7
$\begingroup$

Is there a simple or potentially intuitive explanation for, with the DFT, vector multiplication in one domain being equivalent to circular convolution of the transforms of the vectors in the other domain?

Since a DFT is just multiplication by a (special) square matrix, what about this matrix and matrix multiply allows the above duality?

$\endgroup$
5
$\begingroup$

As you correctly say, the DFT can be represented by a matrix multiplication, namely the Fourier matrix $\mathbf{F}$. On the other hand the DFT "transforms" a cyclic convolution in a multiplication (as all Fourier transform variant as DFT, DTFT, FT have a similar property of transforming convolution to multiplication) and vice versa.

To understand this in the matrix picture, note that also (circular) convolution with a certain sequence can be represented by a matrix multiplication. More specifically this is a circulant matrix, a special kind of a Toeplitz matrix.

so $\mathbf{y} = \mathbf{c} * \mathbf{x}$ with $*$ the cyclic convolution can be written as $\mathbf{y} = \mathbf{C}(\mathbf{c}) \mathbf{x}$ with $\mathbf{C}$ denoting the circulant matrix formed from entries of vector $\mathbf{c}$.

If we "transform" this equation with the DFT (i.e. multiplication by $\mathbf{F}$) we obtain

$\widehat{\mathbf{y}} = \mathbf{F} \, \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H\, \widehat{\mathbf{x}}$

with $\widehat{\mathbf{y}} =\mathbf{F}\mathbf{y}$ and $\widehat{\mathbf{x}} =\mathbf{F}\mathbf{x}$ the respective DFTs (note $\mathbf{F}^H$ represents the IDFT).

The point is now that $\mathbf{F} \mathbf{C}(\mathbf{c}) \,\mathbf{F}^H$ is always a diagonal matrix, because all circulant matrices are diagonalized by the Fourier matrix. This means that the eigenvectors of circulant matrices are just given by the rows of the Fourier matrix.

This is of course consistent with the convolution picture, because the DFT transforms the convolution to an elementwide multiplication. Moreover the diagonal elements of this matrix are just the DFT of $\mathbf{c}$, or, eqivalently, the eigenvalues of the circulant matrix formed from $\mathbf{c}$.

$\endgroup$
  • $\begingroup$ Sure, I just inserted the identity matrix between $C(c)$ and $x$. Note that $F^H F = I$. This is so that in the equation also the Fourier transform of $x$ appears. $F^H F = I$ is because the Fourier matrix is a unitary matrix, just like the DFT is an unitary transform. $\endgroup$ – Andreas H. Jul 31 '13 at 15:17
  • $\begingroup$ Left hand side of x. Start with $y = C(c)x$, multiply by $F$ from left: $\widehat{y} = F C(c) x$ then insert $I = F^H F$ and get $\widehat{y} = F C(c) F^H F x$ which is $\widehat{y} = F C(c) F^H \widehat{x}$ $\endgroup$ – Andreas H. Jul 31 '13 at 15:50
  • $\begingroup$ No, $FCF^H$ is what results from the derivation, $F^H C F$ would be incorrect. $\endgroup$ – Andreas H. Jul 31 '13 at 16:15
2
$\begingroup$

Incidentally, DFT is the only bijective linear transformation that exchanges convolution and termwise multiplication (up to permutation of the coefficients, obviously). This is not difficult to prove, but I have found no reference on this result before I spelled it out in Music Through Fourier Space, Thm. 1.11 (Springer 2016). It is messier in the continuous case because one has to choose well the function spaces involved.

Perhaps this reciprocal could also be proved using circulating matrixes and simultaneous diagonalisation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.