An infinite Toeplitz matrix implements, in principle, acyclic
convolution (which is what we normally mean when we just say
``convolution''). In practice, the convolution of a signal and an
impulse response , in which both and are more than a
hundred or so samples long, is typically implemented fastest using
FFT convolution (i.e., performing fast convolution using the
Fast Fourier Transform (FFT)
[84]F.3). However, the FFT computes
cyclic convolution unless sufficient zero padding is used
[84]. The matrix representation of cyclic (or ``circular'')
convolution is a circulant matrix, e.g.,
As in this example, each row of a circulant matrix is obtained from
the previous row by a circular right-shift. Circulant
matrices are
thus always Toeplitz (but not vice versa). Circulant matrices have
many interesting properties.
F.4 For example, the
eigenvectors of an
circulant matrix are the
DFT sinusoids
for a length
DFT [
84]. Similarly, the
eigenvalues may be
found by simply taking the DFT of the first row.
The DFT eigenstructure of circulant matrices is directly related to
the DFT convolution theorem [84]. The above
circulant matrix
, when multiplied times a length 6 vector
,
implements cyclic convolution of
with
.
Using the DFT to perform the circular convolution can be expressed as
where `
' denotes circular convolution. Let
denote
the matrix of sampled
DFT sinusoids for a length
DFT:
. Then
is the
DFT matrix, where `
' denotes Hermitian transposition
(transposition and complex-conjugation). The DFT of the length-
vector
can be written as
, and the
corresponding inverse DFT is
. The
DFT-eigenstructure of circulant matrices provides that a real
circulant matrix
having top row
satisfies
diag
, where
is the length
DFT of
, and
diag
denotes a diagonal matrix with the
elements of
along the diagonal. Therefore,
diag
. By the DFT
convolution theorem,
Premultiplying by the IDFT matrix
yields
Thus, the DFT convolution theorem holds if and only if the circulant
convolution matrix
has eigenvalues
and eigenvectors given
by the columns of
(the DFT
sinusoids).
Next Section: Inverse FiltersPrevious Section: General LTI Filter Matrix