Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
I presume you haven't seen Bluestein's trick, then? –  J. M. Jan 31 '12 at 4:14
    
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 trick –  user782220 Jan 31 '12 at 5:45
    
Well, one could adapt the reasoning here to the discrete Fourier transform... –  J. M. Jan 31 '12 at 5:59
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 .... –  Dilip Sarwate Jan 31 '12 at 23:46
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. –  Dilip Sarwate Jan 31 '12 at 23:48
show 3 more comments

1 Answer

up vote 1 down vote accepted

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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