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) [84]<sup>F.3</sup>). 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.,

$$\mathbf{h}= \left[\begin{array}{cccccc} h_0 & 0 & 0 & 0 & h_2 & h_1 \\ [2pt] h_1 & h_0 & 0 & 0 & 0 & h_2 \\ [2pt] h_2 & h_1 & h_0 & 0 & 0 & 0 \\ [2pt] 0 & h_2 & h_1 & h_0 & 0 & 0 \\ [2pt] 0 & 0 & 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.^F.4 For example, the eigenvectors of an $N\times N$ circulant matrix are the DFT sinusoids for a length $N$ 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 $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]\isdeftext 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}} &\Leftrightarrow& \underline{Y}[k]=\underline{H}[k]\,\underline{X}[k], \,\forall k\in[0,N-1]\\ &\Leftrightarrow& \underline{Y}= \mbox{diag}(\underline{H})\,\underline{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).