1
$\begingroup$

I was reading about the discrete fourier transform from the CLR algorithms book and I came upon an exercise whose hint confuses me. The exercise reads as follows:

The chirp transform of a vector $a=(a_0,a_1,\ldots,a_n)$ is a vector $y=(y_0,y_1,\ldots,y_n)$, where $y_k=\sum_{j=0}^{n-1}a_j (z^{k})^j$ and $z$ is any complex number. The DFT is therefore a special case of the chirp transform, obtained by taking $z=\omega_n$. Prove that the chirp transform can be evaluated in time $O(n\lg n)$ for any complex number $z$. (Hint: use the equation $y_k = z^{k^2/2}\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$ to view the chirp transform as a convolution.

My question is about what is a convolution. I am familiar with taking two vectors $a=(a_0,a_1,\ldots,a_n)$ and $b=(b_0,b_1,\ldots,b_n)$ and forming the convolution $c=(c_0,c_1,\ldots,c_n)$ where $c_k = \sum_{j=0}^k a_j b_{k-j}$. Here the index of $j$ runs from $0$ to $k$ unlike in the hint given above where the index runs from $0$ to $n-1$. In what sense is the hint above a convolution?

  • 0
    And also you are saying that the use case of the DFT in the algorithms book to multiply polynomials fast is an aperiodic convolution and is not the main usage of the DFT. Most usages of the DFT are in the context of the circular convolution?2012-02-01

1 Answers 1

2

Convolution and the Discrete Fourier Transform:

Suppose $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$ denote two complex-valued sequences of length $n$, and let $a(z)=\sum_k a_kz^k$ and $b(z)=\sum_k b_kz^k$ denote the corresponding polynomials of degree $< n$.

  • The linear or aperiodic convolution of the two sequences is defined as the sequence $(c_0, c_1, \ldots, c_{2n-2})$ of length $2n-1$ where $c_k = \begin{cases}\sum_{j=0}^k a_jb_{k-j}, &0 \leq k \leq n-1\\ \sum_{j=k-(n-1)}^{n-1} a_jb_{k-j}, &n \leq k \leq 2n-2. \end{cases}$ and the corresponding polynomial $c(z) = \sum_k c_kz^k$ of degree $< 2n-1$ equals $a(z)b(z)$.

  • The circular or cyclic or periodic convolution of the two sequences is defined as the sequence $(d_0, d_1, \ldots, d_{n-1})$ of length $n$ where $d_k = \sum_{j=0}^{n-1}a_jb_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1.$ Note that $d_k = \begin{cases}c_k + c_{k+n}, &0 \leq k \leq n-2,\\ c_{n-1}, & k = n-1, \end{cases}$ and the corresponding polynomial $d(z) = \sum_k d_k z^k$ of degree $< n$ equals $a(z)b(z) \bmod (z^n - 1)$ where for future reference we write this as $a(z)b(z) = q(z)(z^n-1) + d(z)$.

  • Let $\omega = \exp(i2\pi/n)$ denote a complex $n$-th root of unity. The Discrete Fourier Transform (DFT) of $(a_0, a_1, \ldots, a_{n-1})$ is $(A_0, A_1, \ldots, A_{n-1})$ where $A_k = \sum_{j=0}^{n-1} a_j \omega^{-jk} = a(\omega^{-k}), ~ 0 \leq k \leq n-1.$ The inverse DFT of $(A_0, A_1, \ldots, A_{n-1})$ is $a_k = \frac{1}{n}\sum_{j=0}^{n-1} A_j \omega^{jk} = \frac{1}{n}A(\omega^{k}), ~ 0 \leq k \leq n-1.$ The inverse DFT of $(A_0B_0, A_1B_1, \ldots, A_{n-1}B_{n-1})$, the term-by-term product of the DFTs of $(a_0, a_1, \ldots, a_{n-1})$ and $(b_0, b_1, \ldots, b_{n-1})$, is $(d_0, d_1, \ldots, d_{n-1})$, the periodic convolution of the two sequences, not the aperiodic convolution. An informal proof of this is that $A_kB_k = a(\omega^{-k})b(\omega^{-k})$ are the values of $a(z)b(z)$ at the $n$-th roots of unity. Since $a(z)b(z) = q(z)(z^n-1) + d(z)$, we know the values of $d(z)$ at the $n$ $n$-th roots of unity, and thus $d(z)$ of degree $< n$ must be the unique polynomial of degree $< n$ that interpolates through these $n$ points.

Chirp signals: The OP asks in what sense $\sum_{j=0}^{n-1}(a_j z^{j^2/2})(z^{-(k-j)^2/2})$ can be considered a convolution? With $\hat{a}_j = a_jz^{j^2/2}$ and $b_j = z^{-j^2/2}$, this is very much like a cyclic convolution $d_k = \sum_{j=0}^{n-1}\hat{a_j}b_{(k-j) \bmod ~n}, ~0 \leq k \leq n-1$ and is a cyclic convolution if $z^{n^2/2} = 1$.