Various definitions of DFT

Have you ever chased an idea, which seemed to just escape your grasp every time you thought it was within your reach? Well, I was supposed to do an assignment about switching between different definitions of DFT (0-centered, Mathematica and Matlab).  And even though I knew what the answer should be (you have got to reverse the DFT sequence and then rotate it in the complex plane, each term by a different angle), I felt there was something going on which I did not understand. I mean, ok this is what I have to do to go from one definition to another, but what does that tell me about the connection between the three?

I kept thinking in terms of reversing and rotating, and yet that connection eluded me. It was only when I started thinking in terms of a change of basis that things began to make more sense. So here is what I finally understood: the columns of the inverse DFT matrix are the basis vectors for the n-dimensional complex space. What we are doing in going from one indexing to another is changing basis and the problem reduces to finding the coefficients of a vector with respect to a changed basis. And that is a simple linear algebra problem.

This way of thinking answers one more thing that was nagging me: the standard book on the subject (Briggs’) says: “The kth DFT coefficient gives the “amount” of the kth mode that is present in the sequence f.”  But periodicity of  a DFT sequence is implied by its definition. Does that mean we have the same “amount” of every nth frequency present?

Of course not! If I think in terms of basis, it tells me that the coefficients w.r.t any basis set (assuming indexing is not changed) remain the same.

So what about the “amount” of a frequency component. This question was answered by my prof. We cannot know what frequencies are being talked about unless we know the length of the interval on which f has been sampled.

Beautiful! Now everything makes so much more sense. And I can sleep without dreaming of DFT matrix.

Reinventing, or at least rediscovering, the wheel can sometimes be sheer pleasure.

This entry was posted in Notes and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s