The convolution theorem for the unitary discrete Fourier transform

I originally wrote up these study notes because I wanted to have handy the properly normalized formulas for the convolution theorem as applied to the unitary discrete Fourier transform (DFT). There are many versions of the Fourier transform. There is the unitary continuous Fourier transform and there are non-unitary versions as well. There are also several discrete Fourier transforms. The normalization constants for the Fourier transform depend on such considerations: unitary vs. non-unitary and discrete vs. continuous.

The continuous unitary Fourier transform for a function ${f: \Bbb R \rightarrow \Bbb C}$ defined on the real line is given by the pair

$\displaystyle \begin{array}{rcl} \hat f(k) &=& \displaystyle\frac 1 {\sqrt {2 \pi}} \int _{-\infty}^{\infty} f(x) e^{-i k x} dx \\ \hat f(x) &=& \displaystyle\frac 1 {\sqrt {2 \pi}} \int _{-\infty}^{\infty} \hat f(k) e^{i k x} dk ~. \end{array}$

The normalization constant ${(2\pi)^{-1/2}}$ guarantees that the ${L^2}$ norm is preserved under Fourier transformation — hence, the above Fourier transform is unitary. The following, more usual convention, for example, is not unitary:

$\displaystyle \begin{array}{rcl} \tilde f(k) &=& \displaystyle\int _{-\infty}^{\infty} f(x) e^{-i k x} dx \\ \hat f(x) &=& \displaystyle\frac 1 {{2 \pi}} \int _{-\infty}^{\infty} \hat f(k) e^{i k x} dk ~. \end{array}$

The above formulas are well known and easy to find. However, the discrete Fourier transform is less used and the unitary version of it even less. There is a normalization constant that appears in the convolution theorem that is not easy to find in the textbooks, so I had decided to write it up for myself.

Consider a function ${f(x)}$ defined for ${x=1,2,\ldots,N}$ . We define the unitary discrete Fourier transform according to

$\displaystyle \hat f(\nu) = \frac 1 {\sqrt{N}} \sum_{x=0}^{N-1} f(x) e^{ -2 \pi i x \nu/N } ~. \ \ \ \ \ (1)$

Now consider that

$\displaystyle \begin{array}{rcl} \displaystyle\frac 1 {\sqrt{N}} \sum_{\nu=0}^{N-1} \hat f(\nu) e^{ 2 \pi i x \nu/N } &=& \displaystyle\frac 1 {{N}} \sum_{\nu=0}^{N-1} \sum_{x'=0}^{N-1} f(x') e^{ -2 \pi i x' \nu/N } e^{ 2 \pi i x \nu/N } \\ &=& \displaystyle\sum_{x'=0}^{N-1} f(x') \frac 1 {{N}} \sum_{\nu=0}^{N-1} e^{ 2 \pi i (x-x') \nu/N } \\ &=& \displaystyle\sum_{x'=0}^{N-1} f(x') \delta_x(x') \\ &=&f(x) ~. \end{array}$

Hence, the inverse transform:

$\displaystyle f(x) = \frac 1 {\sqrt{N}} \sum_{\nu=0}^{N-1} \hat f(\nu) e^{ 2 \pi i x \nu/N } ~. \ \ \ \ \ (2)$

Above, we have used the Kronecker delta function:

$\displaystyle \delta_x(y)= \delta_y(x) = \left \{ \begin{array}{l} 0, \quad x\neq y \\ 1, \quad x=y~. \end{array} \right. \ \ \ \ \ (3)$

Note that the inverse transform is slightly different from the forward transform. There is, in fact, a definition of the Fourier transform known as the involutive unitary discrete Fourier transform, such that it is its own inverse, but I do not further discuss it here.

Let us now prove Plancherel’s theorem, which is often known as Parseval’s theorem in physics. Let us define

$\displaystyle \begin{array}{rcl} \langle{f,g}\rangle &=& \displaystyle\sum_x f^*(x) g(x) \\ \langle{\hat f,\hat g}\rangle &=& \displaystyle\sum_\nu \hat f^*(\nu) \hat g(\nu) ~. \end{array}$

Now consider that

$\displaystyle \begin{array}{rcl} \langle{\hat f,\hat g}\rangle &=& \displaystyle\frac 1 N \sum_\nu \sum_{x,x'} e^{2\pi i \nu (x'-x)/N} f^*(x') g(x) \\ &=& \displaystyle\sum_{x,x'} f^*(x') g(x) \frac 1 N \sum_\nu e^{2\pi i \nu (x'-x)/N} \\ &=& \displaystyle\sum_{x,x'} f^*(x') g(x) \delta_0(x'-x) \\ &=& \displaystyle\sum_{x} f^*(x) g(x) \\ &=& \langle{f,g}\rangle ~. \end{array}$

Putting ${f=g}$ we get

$\displaystyle \big\|f\big\|^2 = \big\|\hat f\big\|^2 ~. \ \ \ \ \ (4)$

We have just proven that the Euclidean norm is invariant under Fourier transformation. In other words, this definition of the Fourier transform is indeed unitary.

Note that

$\displaystyle \delta_0(x) = \frac 1 N \sum _ \nu e^{2 \pi i \nu x /N} \ \ \ \ \ (5)$

from which it follows that the unitary DFT of the Kronecker delta function is

$\displaystyle \widehat \delta_0(\nu) = \frac 1 {\sqrt N} \ \ \ \ \ (6)$

and similarly

$\displaystyle \widehat {\delta_y}(\nu) = \frac 1 {\sqrt N} e^{-2 \pi i \nu y /N} ~~. \ \ \ \ \ (7)$

Now let us look at convolution. We would like the convolution operation ${*}$ to satisfy, in the ${x}$ variable, the identity

$\displaystyle \delta_0(x) * \delta_0(x) = \delta_0(x) ~. \ \ \ \ \ (8)$

The following definition of convolution satisfies the above normalization:

$\displaystyle f*g (x) = \sum_{y=1}^N f(y) g(x-y) ~. \ \ \ \ \ (9)$

where we are assuming that ${g}$ has a periodic extension. In other words,

$\displaystyle g(x+n N)=g(x)~, \quad n\in \Bbb Z~. \ \ \ \ \ (10)$

We need this condition because the index ${(x-y)}$ in ${g(x-y)}$ can assume values outside the interval ${1 \ldots N}$ .

My original reason for the specific concern about the normalization is that the precise statement of the convolution theorem depends on how convolution is defined. Consider the Fourier transform of ${f(x) g(x)}$ , again assuming these functions have periodic extensions.

$\displaystyle \begin{array}{rcl}\displaystyle \frac 1 {\sqrt N} \sum_x f(x) g(x) e^{-2 \pi i \nu x/N} &=& \displaystyle\frac 1 {N^{3/2}} \displaystyle\sum_x \sum_{\nu',\nu''} \hat f(\nu') \hat g(\nu'') e^{-2 \pi i \nu x/N} e^{2 \pi i \nu' x/N} e^{2 \pi i \nu'' x/N} \\ &=& \displaystyle\frac 1 {\sqrt N} \displaystyle\sum_{\nu',\nu''} \hat f(\nu') \hat g(\nu'') \frac 1 N \sum_x e^{2 \pi i x (-\nu + \nu' + \nu'' )/N} \\ &=& \displaystyle\frac 1 {\sqrt N} \displaystyle\sum_{\nu',\nu''} \hat f(\nu') \hat g(\nu'') \delta _0(-\nu + \nu' +\nu'') \\ &=& \displaystyle\frac 1 {\sqrt N} \displaystyle\sum_{\nu',\nu''} \hat f(\nu') \hat g(\nu'') \delta _{\nu - \nu'}(\nu'') \\ &=& \displaystyle\frac 1 {\sqrt N} \displaystyle\sum_{\nu'} \hat f(\nu') \hat g(\nu-\nu') \end{array}$

Note the prefactor, so that

$\displaystyle \widehat {f g} = \frac 1 {\sqrt N} ~~\hat f * \hat g ~. \ \ \ \ \ (11)$

I actually took some time to figure this out, because if we wish to write the convolution theorem as

$\displaystyle \widehat {f g} = \hat f * \hat g \ \ \ \ \ (12)$

then we must give up on the definition in (8).

Hence, for the unitary discrete Fourier transform with convolution defined according to (8), the convolution theorem becomes

$\displaystyle \widehat {f g} = \frac 1 {\sqrt N} ~~\hat f * \hat g ~. \ \ \ \ \ (13)$

2 thoughts on “The convolution theorem for the unitary discrete Fourier transform”

marcos luz on 03/01/2020 at 11:25 said:

This is indeed a quite interesting observation about the Fourier transform (FT), barely mentioned in more “applied” textbooks and therefore not well appreciated by students and even science and technology professionals using FT as tool in very applications. But the present may also raise a relevant broad question: among all possible integral transforms (Fourier and Laplace are just two among many), which is the minimal condition for them to be unitary? I know no general answer to that.

Reply ↓
- Gandhi Viswanathan on 03/01/2020 at 12:12 said:
  
  I had never thought about that… Good question.
  
  Reply ↓

Gandhi Viswanathan's Blog

Physics, Math and Life as a Scientist

The convolution theorem for the unitary discrete Fourier transform

2 thoughts on “The convolution theorem for the unitary discrete Fourier transform”

Leave a Reply Cancel reply

Share this:

Like this:

Related

2 thoughts on “The convolution theorem for the unitary discrete Fourier transform”

Leave a Reply Cancel reply