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
    I presume you haven't seen [Bluestein's trick](http://math.stackexchange.com/a/77156), then?2012-01-31
  • 0
    My question isn't about why Bluestein's trick is true. It's about why can the DFT be used to compute the "convolution" in Bluestein's trick2012-01-31
  • 0
    Well, one could adapt the reasoning [here](https://en.wikipedia.org/wiki/Convolution_theorem) to the discrete Fourier transform...2012-01-31
  • 0
    The convolution here is what is sometimes called a circular or periodic convolution. The convolution that you are familiar with is the aperiodic convolution. Note that your concept of convolution needs some correction: the convolution $c$ of $(n+1)$-tuples $a$ and $b$ is a $(2n+1)$-tuple, not a $(n+1)$-tuple as you have it. The DFT supports circular convolution, not aperiodic convolution. Search for the concept of zero-padding to understand how the DFT can be adapted to compute aperiodic convolutions. Also, consider asking about this on dsp.stackexchange.com2012-01-31
  • 0
    @DilipSarwate Ok so the algorithms book proves the following convolution theorem. For any two vectors $a$ and $b$ of length $n$, where $n$ is a power of 2, $a\otimes b=DFT_{2n}^{-1}(DFT_{2n}(a)\cdot DFT_{2n}(b))$, where the vectors $a$ and $b$ are padded with $0$'s to length $2n$ and $\cdot$ denotes the componentwise product of two $2n$-element vectors. You are saying that its an incomplete statement of the convolution and the DFT?2012-01-31
  • 1
    Your statement about the convolution theorem is correct (though unduly restrictive in that it is not necessary for $n$ to be a power of $2$; $n$ can be any positive integer), but the point you are missing is that the result $a\otimes b$ is a vector of length $2n$ of which as many as $2n-1$ components can be nonzero. In other words, $a\otimes b$ is _not_ a vector of length $n$ padded with $0$s to length $2n$, it is a vector of length $2n-1$ padded with one $0$. The convolution supported by the DFT is circular convolution, not linear convolution, and that is ....2012-01-31
  • 1
    ...and that is why you have to use a DFT twice as long as the vectors, and zero-pad the vectors, so as to use the convolution theorem to get the result of a linear convolution.2012-01-31
  • 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$.