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 $x$ and an impulse response $h$, in which both $x$ and $h$ 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) [83]<sup>6.9</sup>). However, the FFT computes cyclic convolution unless sufficient zero padding is used [83]. The matrix representation of cyclic (or ``circular'') convolution is a circulant matrix, e.g.,

$$\mathbf{h}= \left[\begin{array}{cccccc} h_0 & 0 & 0 & 0 & h_2 & ... ... h_2 & h_1 & h_0 & 0 \\ [2pt] 0 & 0 & 0 & h_2 & h_1 & h_0 \end{array}\right].$$

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.^6.10 For example, the eigenvectors of an $N\times N$ circulant matrix are the DFT sinusoids for a length $N$ DFT [83]. 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 [83]. The above $6\times 6$ circulant matrix $\mathbf{h}$, when multiplied times a length 6 vector ${\underline{x}}$, implements cyclic convolution of ${\underline{x}}$ with $\underline{h}=[h_0,h_1,h_3,0,0,0]$. Using the DFT to perform the circular convolution can be expressed as

$$\underline{y}={\underline{x}}\circledast \underline{h}=$$IDFT$$($$DFT$$({\underline{x}})\cdot$$DFT$$(\underline{h})),$$

where ` $\circledast$' denotes circular convolution. Let $\mathbf{S}$ denote the matrix of sampled DFT sinusoids for a length $N$ DFT: $\mathbf{S}[k,n]\isdef e^{j2\pi k n/N}$. Then $\mathbf{S}^\ast$ is the DFT matrix, where `$\ast$' denotes Hermitian transposition (transposition and complex-conjugation). The DFT of the length-$N$ vector ${\underline{x}}$ can be written as $\underline{X}=\mathbf{S}^\ast\,{\underline{x}}$, and the corresponding inverse DFT is ${\underline{x}}=(1/N)\mathbf{S}\underline{X}$. The DFT-eigenstructure of circulant matrices provides that a real $N\times N$ circulant matrix $\mathbf{h}$ having top row $\underline{h}^T$ satisfies $\mathbf{h}\mathbf{S}= \mathbf{S}\cdot$   diag$(\underline{H})$, where $\underline{H}=\mathbf{S}^\ast\,\underline{h}$ is the length $N$ DFT of $\underline{h}$, and diag$(\underline{H})$ denotes a diagonal matrix with the elements of $\underline{H}$ along the diagonal. Therefore, diag$(\underline{H})=\mathbf{S}^{-1}\mathbf{h}\mathbf{S}=(1/N)\mathbf{S}^\ast\,\mathbf{h}\,\mathbf{S}$. By the DFT convolution theorem,

$$\begin{eqnarray*} \underline{y}=\underline{h}\circledast {\underline{x}} &\Leftr... ...{X}=(1/N)\mathbf{S}^\ast\,\mathbf{h}\,\mathbf{S}\,\underline{X}. \end{eqnarray*}$$

Premultiplying by the IDFT matrix $(1/N)\mathbf{S}$ yields

$$\underline{y}= (1/N)\mathbf{S}\underline{Y}=(1/N)\mathbf{S}\mathbf{S}^\ast\,\mathbf{h}\,(1/N)\mathbf{S}\underline{X}= \mathbf{h}{\underline{x}}.$$

Thus, the DFT convolution theorem holds if and only if the circulant convolution matrix $\mathbf{h}$ has eigenvalues $\underline{H}$ and eigenvectors given by the columns of $\mathbf{S}$ (the DFT sinusoids).