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

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.

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

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).

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University