Talk:Discrete Fourier transform

I can't see the character &#8497, even when I select Unicode encoding from the "view" menu of explorer (unless it's supposed to be an empty box). -rs2 21:25, 24 Mar 2004 (UTC)

It's U+2131 ℱ SCRIPT CAPITAL F = Fourier transform (see Unicode letterlike symbols (http://www.unicode.org/charts/PDF/U2200.pdf)). You can't see it because you don't have a font installed that contains that character. It's nothing to do with the encoding of the Wikipedia page, which was ISO-8859-1. — Gdr, 21:30 2004-03-31.

Normalization constants

This is wrong. The discrete fourier transform is given by

<math>X(w) = \frac{1}{N} \sum_{k=0}^{N-1} x(k) \, e^{-\frac{2 \pi i}{N} w k} \quad \quad w = 0, \dots, N-1<math>

The inverse DFT is given by

<math>x(k) = \sum_{w=0}^{N-1} X(w) \, e^{\frac{2 \pi i}{N} w k} \quad \quad k = 0, \dots, N-1<math>

In both equations, N is the total number of sampling points.

This is purely a matter of convention, as noted in the article. The convention in the Wikipedia article is extremely common (for example, it is the one used in Matlab [1] (http://www.mathworks.com/access/helpdesk/help/techdoc/ref/fft.shtml)). —Steven G. Johnson 03:19, Jan 7, 2005 (UTC)

Hello Steven - about the reason for the 1 and 1/n convention - I see your point that it avoids a multiplication for the DFT but I don't think that an actual algorithm would put the 1/n inside the summation and multiply all n times. It would just perform the summation and then multiply by 1/n. Shouldn't we say that its a combination of avoiding a multiplication for the DFT, AND not having to spend the time calculating the square root? Paul Reiser 18:58, 25 Jan 2005 (UTC)

You have n outputs, therefore you have to multiply n times. You only have to compute the square root once, and furthermore the square root is independent of the data <math>x_k<math> so it can be precomputed. (In principle, there are ways to absorb the scaling into the twiddle factors of the FFT, but this seems rarely done in practice—one has to accomodate the different conventions desired by users, so it is easier to do no scaling it all in an FFT code and leave it to the user. Often, the normalization factor can be absorbed into some other part of a calculation at negligible cost.)

Even putting aside computational considerations, the η=1 scaling is sometimes more convenient than a unitary scaling. For example, in deriving FFT algorithms everyone drops the normalization because it is just an annoyance that can be tacked on later. Or, if you want to interpret your <math>f_k<math> as sinusoid amplitudes it is nice to have an unscaled IDFT. Etcetera...unitarity isn't sacrosanct. —Steven G. Johnson 01:41, Jan 26, 2005 (UTC)

I'm think I'm going to go back to the old definitions without the η's. The η factors are confusing to a new reader, are not conventional notation, are inconsistent with the FFT articles, and we had already stated equivalent information in words. —Steven G. Johnson 01:44, Jan 26, 2005 (UTC)

Ok, I get it about the n times thing. I think we are coming at this thing from two different directions. Your idea of "best" normalization seems to be from an algorithmic point of view, mine is from a mathematical point of view. Casting the DFT as a unitary operator is absolutely the best thing to do from my point of view. All of physics is based on things that are invariant under some transformation or other. When the DFT is a unitary transformation, the dot product, the angle between two vectors, the length of a vector, all are preserved. Viewing the DFT as a unitary operator is like saying it is a simple rigid rotation in space. With the 1,1/n normalization, it is like saying its a rigid rotation plus converting from meters to inches. Its klugy from a mathematical point of view. Ok, thats my rant. I agree that using the η symbols is not the best thing for a new reader to see, and we have to come to a compromise here. How about we do it in 1,1/n normalization, and I put in a section about the unitary normalization and how neat it is. I was about to say I needed to correct some things, but I see you are editing the page as I am writing this so I will check it tomorrow. Paul Reiser 02:51, 26 Jan 2005 (UTC)

I agree that unitarity is often a convenient property (I'm a physicist myself). Stating that it is "absolutely the best thing to do" from a "mathematical perspective" is going too far, though—conventions are are there for convenience, and convenience varies with the mathematical context. (For example, with the unitary normalization the convolution theorem would have an extra constant factor of √n. Or, consider the trigonometric interpolation polynomial, for which the most convenient thing is arguably to have a coefficient of 1 in the IDFT so that the amplitudes f are the sinusoid amplitudes.)

With regard to what to do with the article, it already mentions the unitary normalization in several places. I'm not sure whether adding a whole new subsection would be an improvement. (If any inconsistencies have crept into the article, however, by all means correct them.) —Steven G. Johnson 03:30, Jan 26, 2005 (UTC)

Hello Steven - I put the unitary material into one section, I think it works, but I took the matrix out of the orthogonality section. I'm not sure if you thought it was serving a purpose there, I couldn't see one, but I did see a purpose for the unitary section, in pointing out that it is a unitary matrix (with the proper normalization). Paul Reiser 11:58, 27 Jan 2005 (UTC)

Merge?

Should this article be merged with discrete-time Fourier transform? Michael Hardy 01:34, 2 Jun 2005 (UTC)

I think not. They are as distinct from each other as the Fourier series is from the continuous Fourier transform. (See Fourier_transform#Family of Fourier transforms.) PAR 09:44, 2 Jun 2005 (UTC)

However, I do not see anything wrong with merging discrete-time Fourier transform with Fourier series since the forward discrete-time Fourier transform is just the reverse Fourier series.PAR 10:03, 4 Jun 2005 (UTC)