## Cyclic Convolution Matrix

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.*,

^{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

IDFTDFTDFT

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,

**Next Section:**

Inverse Filters

**Previous Section:**

General LTI Filter Matrix