Talk:Discrete Fourier transform/Archive 1

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

$X(w)={\frac {1}{N}}\sum _{k=0}^{N-1}x(k)\,e^{-{\frac {2\pi i}{N}}wk}\quad \quad w=0,\dots ,N-1$

The inverse DFT is given by

$x(k)=\sum _{w=0}^{N-1}X(w)\,e^{{\frac {2\pi i}{N}}wk}\quad \quad k=0,\dots ,N-1$

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]). —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 $x_{k}$ 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 $f_{k}$ 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)

Actually this issue could be clarified somewhat if somewhere it is explained how sampling (or lack of sampling), and periodicity (or lack of periodicity) relates all four Fourier transforms. --HappyCamper 3 July 2005 22:08 (UTC)

External Reference to Consider

I have an online book about the DFT that is aimed at the beginning undergraduate level: Mathematics of the Discrete Fourier Transform (http://ccrma.stanford.edu/~jos/mdft/) I am looking into splitting out some of the material into articles for the Wikipedia. However, since there is already a fine DFT article at the Wikipedia, I would merely recommend the book as an external reference, especially for "beginners". -- Julius

involutions

Hi StevenJ. You reverted my changes because you liked your own better. Well, I don't. Shall we discuss the matter and collaborate to improve instead of reverting each others changes ?

1. When counting, don't stop after 'secondly'. You state 'several' and leave it to the reader to finish counting.

I've added the word "third" since you feel strongly about it. —Steven G. Johnson

1. You choose your definition of the DFT / IDFT pair arbitrarily and then talk about 'tricks' to connect them. Our readers deserve better than that. Why not take the involution as the basic definition and avoid further trickery ?

No, I choose the Wikipedia definition. And readers are not served by Wikipedia adopting a transform convention that conflicts with what the rest of the world does. These things are conventions—there is no right or wrong, only standard and nonstandard. The Wikipedia definition is very standard, while the involutary transform is not. —Steven G. Johnson

1. The DFT transforms the vector $\ x$ - not the component $\ x_{k}$. There is no such thing as $\ DFT(x_{k}).$ You may talk about $\ DFT(x)_{k}.$

Notation is neither right nor wrong; it can be unclear, inconsistent, misleading, or nonstandard, but not wrong per se. The question is, is DFT($x_{k}$) clear in this context, or do we need to write DFT($[x_{k}]_{k=0\ldots n-1}$) or something similarly verbose? In this case, I think the meaning is hard to mistake. However, I've used the explicit tuple notation in the page to make you happier. —Steven G. Johnson

1. You may use the left arrow to signify the function $\ f=(f(x)\leftarrow x)$. Thus $\ (x^{y}\leftarrow x)$ is a power function, $\ (x^{y}\leftarrow y)$ is an exponential function, $\ (x\leftarrow x^{y})$ is a root, and $\ (y\leftarrow x^{y})$ is a logarithm. Thus you may talk about $DFT(x_{k}\leftarrow k)=DFT(x)$ and revert indexes: $DFT(x_{-k}\leftarrow k),(k\in \mathbb {Z} /n\mathbb {Z} )$

Using $(k\in \mathbb {Z} /n\mathbb {Z} )$ is needlessly technical here, and without it you suffer the same ambiguity in meaning.

1. The notation $\ 1^{\frac {k}{n}}$ is simpler than $e^{\frac {2\pi \imath k}{n}}$. See root of unity. Bo Jacoby 08:08, 26 September 2005 (UTC)

For the DFT, the standard notation in the literature is $\omega _{n}^{k}$. A couple of places in the article already use this notation where the space/clarity gains are significant, since those places are already discussing more advanced concepts. It doesn't make sense to use it in the introductory sections, however, because the minor space gains are outweighed by the barrier they impose on readers unfamiliar with that notation. —Steven G. Johnson 18:16, 26 September 2005 (UTC)

Hi Steven. Wikipedia may be the reader's first meeting with a subject. So it is more important that the text is understandable than that it conforms to the 'rest of the world', meaning the technical or scientific literature. We have three competing notations for a concept which is very important in science: $\ 1^{\frac {k}{n}}=e^{\frac {2\pi \imath k}{n}}=\omega _{n}^{k}.$ The occurrence of the symbols $\ e,\pi ,\imath ,\omega ,$ are scary to the beginner, and perfectly unnecessary. The omega-notation furthermore does not indicate that it depends only on $k/n$ and not on $k$ and $n$ separately. However, everybody knows the number one, and the argument $k/n$ is indispensible, so while the complexity of the notation $\ 1^{\frac {k}{n}}$ is sufficient, the additional complexities of the notations $\ e^{\frac {2\pi \imath k}{n}},\omega _{n}^{k}$ are unnecessary. Furthermore $\ 1^{\frac {k}{n}}$ connects to other branches of mathematics such as the theory of cyclic groups. This insight was new to Linas and he may not be the only one.

The complex conjugation of the input vector connects the fourier transform to the theory of the inner product. The fact that it also makes the transformation involutary is merely another hint that it is the right thing to do.

The fourier series and the fourier integral are limiting cases of the discrete fourier transform for large values of $n$. This connection is historically not the first insight, nor is it the approach of the 'rest of the world', but it is the insight that the beginner might appreciate because it is coherent and simple. I'd like to edit wikipedia to show it, but of cause I won't do it if you revoke it afterwards. I can leave it for you to do, since you feel so much about the control over these Wikipedia articles. Bo Jacoby 12:39, 27 September 2005 (UTC)

I don't think StevenJ (or myself for that matter) want to control the article so much as to create and maintain high a high quality article. The article as it stands is a compromise between a number of people, in its present form its not the way any of us would write it, but thats life on Wikipedia. I think the 1^k/n insight is good and should be included, but I think that the Wikipedia article will only be one of many sources that someone learning the subject will use. I don't know of any source that uses the 1^k/n notation and so the learner will be constantly needing to translate between the Wikipedia article and everyone else. With regards to the "Expressing the inverse DFT in terms of the DFT" I hope I can edit that to conform to the notation of the rest of the article, such as using script F to denote DFT rather than the letters DFT. I also want to remove all "computer tricks" and put them where they belong, in the FFT article, for example. PAR 17:49, 27 September 2005 (UTC)

Regarding the involution-based DFT definition, if you think it is the "right" thing then by all means publish a paper and convince the rest of the world (although you will have a very hard time of it). In all cases, Wikipedia is not the right place for promulgation of new standards, however persuasive you find them (see Wikipedia:No original research). —Steven G. Johnson 23:30, 27 September 2005 (UTC)

PAR, regarding the "computer tricks" — ways to compute the IDFT from the DFT are simply useful general properties of the transform. They are have nothing to do with FFTs per se, although they are sometimes used to obviate the need for programming separate inverse FFTs. Because of that, I don't see any better place to put them than in the DFT article. (Regarding script F vs. DFT, I'm agree that it should be changed and I will do so ASAP...I had totally forgotten that the article had already defined a notation for this, duh!) —Steven G. Johnson 23:30, 27 September 2005 (UTC)

Cleanup

1. Somewhere the fourier transform of x was called f, and elsewhere it was called X. I have changed f to X. I also changed DFT into script F in accordance with Stevenj.

Most Wikipedia pages on DFT-related subjects currently use the notation that the DFT of x is f; changing it everywhere would be pointless. Therefore, we should primarily stick to that for consistency. On the other hand, when we have the transform of x and y, since we need two letters X and Y are fine—there's nothing mathematically wrong with using a different letter, as long as it is clearly stated in the text. Script F is useful in equations, but using "DFT" as the name of the transform in English is preferable. —Steven G. Johnson

I agree with StevenJ PAR 20:12, 28 September 2005 (UTC)

I should also say that I, personally, would greatly prefer the x -> X notation. I would also prefer to use k as the output index, and j as the input index...or better, N as the transform size and n as the input index (to avoid confusion between j and i). I tried to do this early on but was outvoted, and at this point changing it everywhere would be too much hassle. —Steven G. Johnson 17:18, 28 September 2005 (UTC)

I agree with that and I would be willing to do the changes. PAR 20:12, 28 September 2005 (UTC)

PAR, take a closer look at the sheer number of articles that would need to be changed. (See Category:Fourier analysis.) —Steven G. Johnson 22:40, 29 September 2005 (UTC)

1. I think that the idea of cyclic indexes should be introduced generally at an early stage.

I agree that the implicit periodic boundary conditions should be discussed explicitly, probably under "Properties". —Steven G. Johnson

Yes PAR 20:12, 28 September 2005 (UTC)

1. I don't agree that the trigonometric polynomial is unique. The function e^(2 pi i(n-1)x) differ from e^(-2 pi i x) even if they match at the sampled points. This phenomenon is called 'aliasing'.

Note that it says the unique function of this form, so the article is correct as stated. The aliased polynomials are of a different form. —Steven G. Johnson

On the other hand, I suspect that it is not the same as the trigonometric interpolation polynomial used in practice. In practice, people generally use j from -n/2+1 to n/2, which has the important property of interpolating real inputs to a real function, and also uses the minimum-frequency interpolation. So, probably we should give this form instead and make a note of the different possible formulations. —Steven G. Johnson

1. The unitaryty section still uses a different definition of script F.

It could use F_u or something like that to distinguish...however, it is probably preferable for the section to simply clearly state that it is using a different normalization convention than the main transform definition in the article, but to emphasize that it is essentially the same transform. —Steven G. Johnson

I agree with this and will change it, maybe to U for "unitary matrix"

The problem I have with U is that there is no visual connection with F, even though it is the same transform (essentially), which is why I suggested F_u or just saying in words that it is a different normalization. —Steven G. Johnson 22:17, 29 September 2005 (UTC)

1. I think that this article is very important and should be made perfect. Bo Jacoby 08:42, 28 September 2005 (UTC)

Everyone else thinks it should be a terrible article, so you are outvoted. —Steven G. Johnson 17:09, 28 September 2005 (UTC)

AT LAST! I was getting tired of being so agreeable. I disagree, Bo Jacoby is right. PAR 20:12, 28 September 2005 (UTC)

Hi Steven. The article is terrible: confusing, inconsistent, incomprehensible and far too long. Even if it is not mathematically wrong to change notations and definitions in the middle of an article, it is no good to the reader. I'd like very much to help in cleaning it up, but when you just revoke everything I do, you cannot be helped. I'm really sorry. Bo Jacoby 07:29, 29 September 2005 (UTC)

Bo - why don't you pick out one particular correction, maybe the biggest one in your mind, that you would like to make. Then we can discuss it. If you convince me, then Steven will probably accept it. If you dont, then hopefully you will accept it. Then we can go on to the next problem. What is the most "confusing, inconsistent, incomprehensible" aspect of the article? PAR 18:42, 29 September 2005 (UTC)

PS - Please realize that this is one of a "collection" of related articles, which include Continuous Fourier transform , Fourier series and discrete-time Fourier transform. These articles should have consistent notation as much as possible, and anyone who suggests a radical change in one better be ready to do the work required to change all, and in a relatively error free manner. That implies a thorough understanding of all four articles. PAR 18:52, 29 September 2005 (UTC)

Don't forget all of the fast Fourier transform articles (which includes several articles on particular algorithms). Not to mention discrete cosine transform, discrete Hartley transform, and probably others I am forgetting. —Steven G. Johnson 21:43, 29 September 2005 (UTC)

Thank you for your suggestion, PAR. I'll pick out one particular correction. It is certainly not the biggest in my mind, for that would be the union of all the changes that I have in mind, but it is the first one that I stumble on while reading. It was stated that the word 'sequence' would be used in the meaning of 'vector'. Then the reader could have the burden to remember this and translate 'sequence' into 'vector' while reading. I think this suggests the simple edit of changing 'sequence' to 'vector', taking the burden from the shoulders of the reader. Let me know if anyone disagrees. Bo Jacoby 07:55, 30 September 2005 (UTC)

Vector or sequence

Bo - Before I revert some of your edits, let me explain myself. A sequence is an ordered set of numbers, and that's about it. A vector is a mathematical object which has associated operators etc. and by a logical process it can be deduced that if you define a set of basis vectors (a coordinate system), you can represent a vector in terms of this basis set by a sequence. The sequence is not the vector, at least from a mathematicians or a physicists point of view. It is from a computer programmers point of view, I think, but this is a mathematical article. That means the statement:

The vector of n complex numbers x₀, ..., x_n−1 are transformed into the vector of n complex numbers f₀, ..., f_n−1 by the DFT according to the formula:

is not correct, "vector" should read "sequence". There is no such thing as a "vector of complex numbers", only a sequence of complex numbers that may or may not represent a vector, depending on whether a coordinate system and all the vector operators have been defined. The bottom line is that the DFT operates on sequences. It is often very helpful (and interesting) to assume that the sequences are representative of vectors. The DFT then can be thought of as a linear vector operator, etc. etc. The article is a bit sloppy in this regard and needs to be fixed. PAR 10:38, 30 September 2005 (UTC)

Hi PAR. That subtle distinction between sequence and vector was not at all supported by the original version of the article. On the contrary it was explicitely stated that 'sequence' means 'vector'. $\mathbb {C} ^{n}$ is a vector space over the field $\mathbb {C}$. So the elements are vectors. These vectors are subject to discrete fourier transforms, which are linear (or, preferably antilinear) transformations of the vector space. The limiting cases of the DFT where $n\rightarrow \infty$, such as the fourier integrals and the fourier series, are still linear or antilinear transformations of complex vector spaces. So I don't agree that any distinction between 'sequence' and 'vector' is neither necessary, nor useful, nor easy to explain. The better way to get rid of the sloppyness is to abandon the concept of 'sequence' in this context. Bo Jacoby 12:21, 30 September 2005 (UTC)

I agree, that distinction should be made more clear. However, I still say that the DFT fundamentally operates on sequences which may or may not be sequences of vector components. I don't need to know whether a sequence of complex numbers represents a vector in order to perform a DFT on that sequence. A sequence of complex numbers is not necessarily $\in \mathbb {C} ^{n}$ PAR 14:38, 30 September 2005 (UTC)

PAR, as soon as you say that the DFT is a linear operator, this immediately implies that you are talking about an operator on a vector space. So, I agree with Bo in that I don't think it's very useful to talk about DFTs that do not operate on vector space. On the other hand, we are not talking about any vector space in general; we are talking about the particular vector space $\mathbb {C} ^{n}$ formed of a sequence of complex numbers (where addition and multiplication are defined in the natural way). Moreover, the abstract (non-spatial) definition of a vector space may be unfamiliar to many readers, and because of that I suspect it is a gentler introduction to begin by calling it a "sequence" of inputs. (There's certainly nothing mathematically incorrect about calling it a sequence.) So, while I disagree in part with PAR's reasoning, I agree with his conclusion (that the previous wording is arguably better). —Steven G. Johnson 17:43, 30 September 2005 (UTC)

Ok, I see your point, once you have the transform, you've implicitly defined the operators that make the sequence a vector space. It still grates my sensibilities, I mean there are so many properties of the DFT that aren't of a vector nature, like the shift property. Should we be using "vector" in this instance? I don't think so. Should we only use vector when its a property of a vector space or some higher-ordered space (eg metric) and use sequence otherwise? The previous wording mixed it up, but was there a method to it? PAR 21:08, 30 September 2005 (UTC)

A cyclic shift is just a unitary operator (i.e. a "rotation") on the vector space, as is multiplication by a linear phase. I'm not sure what you mean by properties "of a vector nature". I still don't see the problem with calling it by the more-familiar term of "sequence" in addition to the more-technical term of "vector", though. As George Orwell pointed out in 1984, synonyms (and their slightly differing shades of meaning) make language more expressive, not less. —Steven G. Johnson 01:55, 1 October 2005 (UTC)

Ok, see your point. Its between you and Bo, then, but if I have to break a tie, I would say the old way was good, except a little longer note than "sequence and vector are used interchangeably" would be needed. PAR 14:27, 1 October 2005 (UTC)

I agree with Steven that the discrete fourier transform operations are vector operations. Any finite dimensional vector space over the field of complex numbers can be subject to the discrete fourier transform by chosing a basis, so PAR's feeling that the discrete fourier transform applies to sequencies rather that to abstract vectors is incorrect. Though I generally agree with Orwell about synonyms, the connection between concepts and words is more precise in mathematics than in everyday language. I agree with Steven that one concept is logically sufficient, but we disagree about using two words. To me using two words for one mathematical concept is an unnecessary complication, and this very discussion confirms that it does introduce misunderstanding. Bo Jacoby 08:14, 3 October 2005 (UTC)

The shift theorem

A second suggestion. Why not simply write: ${\mathcal {F}}(\{x_{k}e^{{\frac {2\pi i}{n}}km}\})_{j}={\mathcal {F}}(\{x_{k}\})_{j-m}$ and ${\mathcal {F}}(\{x_{k-m}\})_{j}={\mathcal {F}}(\{x_{k}\})_{j}e^{-{\frac {2\pi i}{n}}jm}$ instead of: if ${\mathcal {F}}(\{x_{k}\})_{j}=f_{j}$ then ${\mathcal {F}}(\{x_{k}e^{{\frac {2\pi i}{n}}km}\})_{j}=f_{j-m}$ and ${\mathcal {F}}(\{x_{k-m}\})_{j}=f_{j}e^{-{\frac {2\pi i}{n}}jm}$ ? The f is unnecessary. Bo Jacoby 09:02, 3 October 2005 (UTC)

I am against that - its a true statement, but its significance is not as immediately obvious. A reader is liable to look at the first one and wonder "so what?" but looking at the same involving f, its immediately clear: multiply the input by the exponential factor amounts to shifting the output. PAR 20:50, 3 October 2005 (UTC)

Different readers look differently on things. I just see the f as a useless complication which the author should have eliminated himself instead of leaving it to the reader. Bo Jacoby 09:27, 4 October 2005 (UTC)

The DFT as a unitary transformation

This section introduces a 4th notation for the fourier transform : The primed index: $\ x_{j'}$. Why not reuse one of the 3: ${\mathcal {F}}(\{x_{k}\})_{j}$, $\ f_{j}$, $\ X_{j}$. Further cleanup may reduce the number even more, hopefully to one. Bo Jacoby 09:25, 3 October 2005 (UTC)

I agree. The point of the primed index rather than the primed vector is to emphasize that the vector has not changed, only its components have, as a result of a coordinate system change. This is in the flavor of Einstein notation for tensors, but it shouldn't be introduced here out of the blue. Either introduce it with explanation or stick to the old notation. (Yes, I am the one that wrote it that way) PAR 20:50, 3 October 2005 (UTC)

Any linear bijection defines a change of coordinate system. That is an important point. It should be explained somewhere in WP, but not necessarily here. Bo Jacoby 09:39, 4 October 2005 (UTC)

Introduction. The only important thing

Says: "The only important thing is that the DFT and IDFT have opposite-sign exponents, and that the product of their normalization factors be 1/n." The words "The only important thing" indicate that only one thing is important. The explanation gives two things. It is depressing to the reader to accept the fact that the author has difficulties in counting to two.

Yes PAR 20:50, 3 October 2005 (UTC)

The opposite-sign exponent thing is not important, because the involutary DFT has DFT=IDFT, with equal exponents. Bo Jacoby 11:52, 3 October 2005 (UTC)

The "involutary DFT" is a different operator than the usual DFT. The two things remain important for the usual DFT, and I don't think we should make this an article about the involutary DFT disguised as the usual DFT. PAR 20:50, 3 October 2005 (UTC)

Consider the important special case of a sequence of real numbers x being transformed according to the formula $n^{-{\frac {1}{2}}}\sum _{k}{x_{k}e^{\frac {2\pi ijk}{n}}}.$ How is this formula generalized to a sequence of complex numbers x ? There are two options : $n^{-{\frac {1}{2}}}\sum _{k}{x_{k}e^{\frac {2\pi ijk}{n}}}$ and $n^{-{\frac {1}{2}}}\sum _{k}{x_{k}^{*}e^{\frac {2\pi ijk}{n}}}.$ Both formulae generalize the real case. They are not that different. The lazy mathematician choses the first one because then he dosn't need to modify the formula. The careful mathematician is guided by algebraic simplicity: Because the second one is involutary and the first one is not, the second one must be chosen and the first one sacrificed on the altar of Occam. PS. Note that I resisted the temptation to write $n^{-{\frac {1}{2}}}\sum _{k}{x_{k}^{*}1^{\frac {jk}{n}}}.$  :-) Bo Jacoby 08:42, 4 October 2005 (UTC)

I don't think the DFT as it stands is the result of early muddled thinking being carved in stone. The DFT is a linear operator while the involutary version is not. If $T(x)$ is the involutary operator then $T(ax+by)=a^{*}T(x)+b^{*}T(y)$. The linearity of the DFT is vitally important. PAR 13:08, 4 October 2005 (UTC)

"Early muddled thinking being carved in stone" it is. I love your poetry! The better generalization of the concept of a linear operator on a real vector space is that of an antilinear operator on a complex vector space. The antilinearity gives precisely what you need. (The name 'antilinear' is ill chosen, however, because it seems to imply that it is the opposite of linear, which it is not.) Bo Jacoby 13:28, 4 October 2005 (UTC)

Well, it doesn't matter, we are not talking about this article any more, we are talking about another article "Involutary DFT" or something. This article is about the DFT, which is linear. But I don't understand what you mean by "what you need" - could you explain that. Also, do you have any references I could look at? PAR 20:42, 4 October 2005 (UTC)

Bo, please go read Wikipedia:No original research. Then read it again. If you are so convinced that the involutary definition is a good thing, then great! But Wikipedia is not the place to push new standards, or anything new for that matter. Go publish an article or two, convince people that it is worthwhile (i.e. see whether your article is ever cited), and then come back and write Involutary DFT. This has nothing to do with whether the involutary thing is a good idea, so that argument is pointless here. —Steven G. Johnson 00:44, 5 October 2005 (UTC)

Steven, after studying No_original_research#Primary_and_secondary_sources I think you are completely wrong. I quote: Research that consists of collecting and organizing information from existing primary and/or secondary sources is strongly encouraged... "No original research" does not mean that experts on a specific topic cannot contribute to Wikipedia. Indeed, Wikipedia welcomes experts and academics. This means that a new calculation or a new notation or an alternative definition is not considered 'original research' in this context. It does not rely on information which is inaccessible to you or to anybody else. I am very flattered that you consider the involutary fourier transform to be original research. If I claim that I have made an invention, I expect everybody to object against it saying that it has been done before, or that it is trivial, so I should not consider myself an original scientist. Now the situation is up-side down. I personally don't believe that the involutary fourier transform is original research on my part. I consider it fairly trivial. I merely point out a minor error in one of your definitions of the fourier transform: one missing asterisk. It can easily be corrected. It is no big deal. I don't consider this to be original research. But you do ! Thank you very much, I'm honored and pleased. Bo Jacoby 08:07, 5 October 2005 (UTC)

The definition of prohibited original research, from that page, is:

The phrase "original research" in this context refers to untested theories; data, statements, concepts and ideas that have not been published in a reputable publication; or any new interpretation, analysis, or synthesis of published data, statements, concepts or ideas that, in the words of Wikipedia's founder Jimbo Wales, would amount to a "novel narrative or historical interpretation".

The involutary DFT definition is a concept or idea that has not been published in a reputable publication; or, if you prefer, it is a new interpretation or synthesis of the standard DFT concepts. Hence "original research". (This has nothing to do with whether it is a good idea, or whether you could get it published in a reputable journal.) It is certainly a indisputed fact that one can define such a transform, and it is (somewhat) reasonable to mention this fact in passing (as we do), if only to highlight the connection with the discrete Hartley transform. However, promoting it as a new transform definition, especially replacing the standard DFT definition as you seem to want, goes beyond what is acceptable practice in Wikipedia. —Steven G. Johnson 16:56, 5 October 2005 (UTC)

PAR, what you need is expanding the expression T(ax+by). In the real case it is aT(x)+bT(y). In the complex case it can be either aT(x)+bT(y) or a*T(x)+b*T(y). In both cases T(ax+by) is evaluated, and that is what is needed. Bo Jacoby 08:07, 5 October 2005 (UTC)

Introduction. Definition

The introduction should give a short answer to the short question: "What is the discrete fourier transform?". Smalltalk should be avoided here. Using the involutary DFT as the definition will do this, and also save the The Plancherel theorem from being mentioned twice in the article. Bo Jacoby 11:52, 3 October 2005 (UTC)

Some history on this article: I changed the definition to include two general normalization constants, constrained only by the fact that their product be 1/n. StevenJ then argued that this was too much of a jolt for someone trying to use Wikipedia as one source among many, an argument which I now agree with. On this basis, we should use the most common definition in the introduction, then expand from there. So that means, in my mind, introducing with either (1,1/n) (the present normalization) or (1/√n,1/√n) (the unitary normalization). The present normalization is appealing to algorithmic types, because you don't need to calculate square roots. The unitary is appealing to physics types because it is symmetric, and analogous to a rigid rotation in Euclidean space, all sorts of things are conserved, dot product, angles, etc. But, given the present normalization, the Plancherel theorem needs to be stated in the present normalization, and then restated to illustrate the efficacy of the unitary normalization. PAR 20:50, 3 October 2005 (UTC)

(PAR, I'm a physicist myself. In physics, you rarely use the discrete version of the transform at all for theoretical work, so your argument is a bit strange. The DFT in my experience is mainly used for computation, and occasionally for expression of discrete convolutions, in which cases the unitary normalization is actually often not the most convenient form as I mentioned below. —Steven G. Johnson 04:42, 5 October 2005 (UTC))

If your programmer wants to spare his computer from computing the square root, by all means, let him code a fast fourier transform subroutine called SQRT_FFT computing √N*DFT(X). It is no excuse for the mathematician to make non-unitarian or non-involutarian definitions. The unitarity and involutarity is appealing to every user, who neither wants to remember two versions of the Plancherel theorem, nor to bother about the difference between DFT and IDFT. Bo Jacoby 12:57, 4 October 2005 (UTC)

Unitarity is one convenient property. The fact that you apparently think it is the only convenient property tells me that you've never done much digital signal processing. For example, putting the 1/n factor in the idft (or only on the dft) makes the convolution theorem come out in a simpler form. (This is probably why Matlab, for example, uses the same convention as in Wikipedia.) From my own personal experience, in talking about FFT algorithms to compute the DFT (which themselves are a rich source of interesting mathematics and not just a practical "programming" matter), the normalization factors are an annoyance that is universally omitted. (See above re: involution form.) —Steven G. Johnson 00:28, 5 October 2005 (UTC)

PS. From a programming perspective, the computation of the square root is irrelevant as it is only done once. More expensive are the 2N multiplications. —Steven G. Johnson

Actually I do have FFT-experience. I completely agree on your PS that the time for taking the square root is epsilon. But the time for the 2N real multiplications is neglectible too because the inner loop of the FFT requires Nlog(N)/log(2) complex multiplications, so this inner loop is more timecomsuming when N is a large number. When N is not a large number everything is fast, so nothing matters. Of cause you know all that. The convolution theorem asserts that the transform of a convolution is the product of the transforms, so the convolution is the transform of the product of the transforms. Can that really be simplified? Please show me. I don't think that unitarity is the only convenient property. Involutarity is nice too, because it is timeconsuming to debug the error of having chosen the wrong one of IDFT and DFT. Not having this to worry about makes programming safer. Bo Jacoby 08:39, 5 October 2005 (UTC)

That statement about the convolution is no longer true if you use the unitary normalization. You either have to change the definition of convolution, or have an extra sqrt(N) factor in the convolution theorem. But of course, you knew that? —Steven G. Johnson 16:23, 5 October 2005 (UTC)

I was mistaken. Thank you for telling me. Bo Jacoby 11:54, 6 October 2005 (UTC)

By the way, in practical circumstances the scaling is not quite so negligible as you imagine, especially in the common case where it is implemented as an extra pass over the array (due to the memory implications more than the arithmetic cost), because the number of passes over the array is quite small already (even though it grows logarithmically) for an optimized FFT. It is possible to absorb the normalization into the twiddle factors, but this has other disadvantages (e.g. the same twiddle factors can't be re-used for the forward and inverse transforms). It is just as efficient (or more efficient), and more flexible, to absorb it into the user's computations. —Steven G. Johnson

Implement any variation of the discrete fourier transform to suit your needs of saving computer time, but stick to one definition and explain your subroutine in terms of that. Bo Jacoby 11:54, 6 October 2005 (UTC)

As another example of a Fourier variant where the unitary normalization is not the most convenient, by the way, consider the Fourier series (where almost no one uses a normalization corresponding to the unitary FT). Your "one true normalization" crusade is just not sensible, I think. —Steven G. Johnson

Yes. Here the symmetry is broken. The coefficients of the fourier series are integrals. Yet my point is the same as before: define one discrete fourier transform and express everything else in terms of that, instead of confusing the reader regarding the meaning of the word. My 'crusade' is for simplicity and clarity, and you are not my opponent in that respect. Bo Jacoby 11:54, 6 October 2005 (UTC)

Initially the article did use one definition, the one at the top. (In my experience this definition is by far the most common in actual practice. It makes things like the convolution theorem come out more nicely.) Then one section was added to say how a unitary normalization has some advantages in expressing certain things in a nice form. I think this is reasonable — indeed, different conventions have different advantages and disadvantages, and it is a service to readers to point this out. It does not make the article "unreadable", especially since the one place where a different convention is used is confined clearly to one sub-section. The alternatives are (a) don't present the unitary representation at all, which misses out on those nice expressions or (b) adopt the unitary representation everywhere, which is at odds with common practice and is inconvenient for actual usage. —Steven G. Johnson 15:50, 6 October 2005 (UTC)

Connection to the continuous fourier transforms

My next suggestion for improvement of the article. Some people consider the discrete transform to be a special case of the continuous transform, when generalized to distributions like the dirac delta 'function'. I think it is better to consider the continuous transformations as limiting cases of the discrete transformation, because then the reader doesn't need to know about integration but can just consider a large value of n. Consider the ring of integers $\mathbb {Z}$, the ideal of multipla of n $n\mathbb {Z}$, and the quotient ring $\mathbb {Z} /n\mathbb {Z}$. The vector space in question is $\mathbb {C} ^{\mathbb {Z} /n\mathbb {Z} }.$ The indexes $k\in \mathbb {Z} /n\mathbb {Z}$ can be represented by integers from 0 to n-1, or from 1 to n. The indexes $k\in \mathbb {Z} /2n\mathbb {Z}$ can be represented by integers from -n to n-1. Substituting $\ t=kn^{-1}\in (\mathbb {Z} /n\mathbb {Z} )/n\subset (\mathbb {R} /\mathbb {Z} ),dt=n^{-1}$ into $n^{-1}\sum _{k=0}^{n-1}x_{k}^{*}1^{\frac {jk}{n}}$ gives the limit $\int _{0}^{1}x(t)^{*}1^{jt}dt.$ Bo Jacoby 12:04, 5 October 2005 (UTC)

That's a lot of unnecessary technical notation just to say that one possible limit of the sum is the integral for the Fourier series (note that you haven't gotten to the continuous Fourier transform yet, for which you have to be much more careful with your limit process...even here one really needs some caveats about convergence). It is reasonable to add a sentence saying that, for many applications, the DFT is used as an approximation for the discrete-time Fourier transform (which in turn is used an approximation for the continuous Fourier transform of band-limited signals) or the Fourier series, which are related by appropriate limits for well-behaved signals. (This was already there, somewhat, in discussions of spectral approximation and partial differential equations, and I've expanded it slightly.) —Steven G. Johnson 16:33, 5 October 2005 (UTC)

For the continuous transform, choose the dimension to be an even square number: $4n^{2}$. Substituting

$t={\frac {k}{2n}},\quad dt={\frac {1}{2n}},\quad \nu ={\frac {j}{2n}}$

into

${\frac {1}{2n}}\sum _{k=-2n^{2}}^{2n^{2}-1}x_{k}^{*}1^{\frac {jk}{4n^{2}}}$

gives the limit

$\int _{-\infty }^{\infty }x(t)^{*}1^{\nu t}dt,\qquad -\infty <\nu <\infty .$

Note that $e,i,\pi$ does not appear in this expression for the unitary involutary continuous fourier transform. (The asterisk signifies complex conjugation). Bo Jacoby 12:46, 6 October 2005 (UTC)

Oh, I wasn't doubting that you can do this. Or, once you have the Fourier series for a length L you can take L to infinity. The problem with positing this as a formal limit process, however, is that it is a little too glib. More care is required to ensure (and even to define) convergence of the limits. It would be great to have a nice article on this in Wikipedia, but it would really be an article in its own right. (And the 1^{1/n} notation, of course, should not be used because it is very nonstandard. Worse, it redefines standard symbols because 1^{1/n} = 1 in the usual branch cut. But that issue has, I hope, been settled in Root of unity.) —Steven G. Johnson 15:58, 6 October 2005 (UTC)

1. In the context of discrete fourier transform it is interesting to compute a finite sum approximately by means of a known integral. That is uncomplicated. 2. In the context of integration theory, the integral is defined as a limit of a sequence of finite sums. That is where all the complication belong. 3. Regarding $1^{x}$ : You are not expected to change your mind, but the mathematicians following you may not feel the same way as you do. Today's nonstandard original reseach may be tomorrow's standard notation. When contempleting your life's net value to humanity you may count your battle against progress as a negative contribution, but while there is death, there is hope. 4. Surely the usual branch cut is redefined. That was no holy cow. $f(z)=z^{x}$ is multivalued, and that cannot be helped in general. The usual branch cut leaves unpleasant and unnatural discontinuities. The conventional choice that $z^{x}$ is nonnegative real for nonnegative real z is natural when working with real numbers. The conventional choice that $1^{x}=1$ is utterly unimportant. It is not used in practice. Why write $1^{x}$ instead of 1 ? The notation $1^{x}$ is free to be redefined to something useful. The expression $e^{2\pi i}$ is repeated endlessly in technical and mathematical litterature, and a many readers get confused. Where did $e$ and $i$ and $\pi$ come from ? Because $e^{2\pi i}=1$ , then $e^{2\pi ix}=1^{x}$ is a natural and useful convention. Bo Jacoby 11:27, 7 October 2005 (UTC)

1. Regarding the limits, you are oversimplifying; even things like the Fourier transform of 1 correspond to integrals that are not absolutely convergent and must be defined with care. (Or then there are famous examples like the function that is 1 on the rationals and 0 on the irrationals; if you treat its integral as the limit of a discrete sum, you'll get the wrong answer.) Handwaving is fine, of course, to get a general intuition, but a proper treatment will require an article in its own right. (Books have whole chapters on this stuff.)

2. Of course, conventions are merely that and can be redefined. But not by Wikipedia. For the umpteenth time, please take your notational revolutions elsewhere. —Steven G. Johnson 15:45, 7 October 2005 (UTC)

Bo - I have to agree with Steven - and I am definitely not used to being on the conservative side of a revolution, and I am not used to agreeing with Steven so often in so short a space of time.

• 1^x is used implicitly when the single valued definition of exponentiation is given as $z^{s}=\exp(s\,\ln(z))\,$ where ln is the usual single valued definition of the natural logarithm. 1^x is not free to use.

• A branch cut leaves unpleasant discontinuities no matter where you make the cut.

• I agree an article explaining how the various transforms can be seen as limiting cases of each other would be a good, but separate article.

• Again, this article is about a particular subject - the usual DFT, not the involutary DFT. It should not be presented as anything but.

• A good revolutionary has to know how and where to join battle to maximum effect. If you were an American revolutionary, you would not sail to the north pole and howl at the moon. This ain't the place, we're not the enemy. You need to publish papers, GOOD papers, and introduce your notation memes there, and if they are robust their adoption will be inevitable.

• Just in case you succeed, I have this idea - no joke - the metric tensor is really just the unit tensor, so its covariant components should be represented in Einstein notation as $1_{ij}\,$. Unitary transformations are really just the metric tensor with mixed coordinates, so all unitary tensors should have their covariant components written like $1_{ij'}\,$ where prime coordinates signify a different coordinate system from unprimed. These tensors are simply index changers so you have expressions like $1_{i}^{j'}A_{j'}=A_{i}\,$. Its obvious that 1 is the right thing to use. Using g or whatever is a less natural and informative notation. Come the revolution, I'll be dead and gone, but can I count on you to implement this as well? It would be such a comfort when contemplating my life's net value to humanity. PAR 16:07, 8 October 2005 (UTC)

to Steven. The discrete fourier transform of x(t)=1 is $X(\nu )={\sqrt {N}}[\nu =0]$, (using Iverson bracket), while the continuous fourier transform of 1 requires a definitional extention of the concept of a function. The indicator function of the rationals, $1_{\mathbb {Q} }$, does not appear as a limit of discrete functions. The complications of definition belong to the article Distribution (mathematics). The complications of integration theory belong to the article Lebesgue integration. No such complication belong to discrete fourier transform. Bo Jacoby 10:27, 10 October 2005 (UTC)

Sigh. My point is that the expressing the continuous Fourier transform as the limit of the DFT inevitably involves such advanced concepts. It isn't obvious or elementary and one should be cautious about presenting it as such. —Steven G. Johnson 16:38, 10 October 2005 (UTC)

I respectfully disagree. What can be easily done should be easily done. Advanced cases may be postponed. Problems should not be solved until they appear. Bo Jacoby 11:06, 11 October 2005 (UTC)

to PAR.

• The 'usual single valued definition of the natural logarithm' is not that usual. See Natural_logarithm#Derivative.2C_Taylor_series_and_complex_arguments. Until you provide a reference where the interpretation $1^{x}=1$ is used, the interpretation $1^{x}=e^{2\pi ix}$ is free to be used without misunderstanding.

I'll work on it, but your statement is wrong. Its not until I provide a reference that its free to use. I'm not that much of an authority. PAR 22:45, 10 October 2005 (UTC)

You will not misunderstand it. Who will ? That is the question. Bo Jacoby 11:06, 11 October 2005 (UTC)

• The concept of branch cut is outdated and being replaced by Riemann surface. So the argument, that $1^{x}$ violates the 'standard branch cut', is not decisive. Note that the definition $z^{x}=\exp(x\log(z))$ leads to a singlevalued interpretation of $e^{x}$ only after chosing one of the values of $\log(e)$, namely 1, rather than for example $1+2\pi i$. Likewise a singlevalued interpretation of $1^{x}$ is made by chosing one of the values of log(1), namely $2\pi i$, rather than for example 0.

I don't think thats true. The idea of the branch cut being a sort of artificial thing to yield a single valued function from a multi-valued function is very old. Also, I specified to begin with that the logarithm was the single-valued logarithm, so that log(e)=1 automatically. PAR 22:45, 10 October 2005 (UTC)

• The limits leading to fourier series and continuous fourier transforms could be given in a few lines, which I might write myself when I feel more confident that it will not be removed immediately. I encourage your writing separate articles, of cause.

It certainly won't be removed as long as its correct, yet not revolutionary. PAR 22:45, 10 October 2005 (UTC)

• There is no such thing as the usual DFT but a mess of related definitions, even in the present WP article.

As the article notes, a few slight variations are common. However, some variations are definitely not a "usual" variant of the DFT. For example, anything which is not linear. —Steven G. Johnson

Are you aware that the restriction of the involutary fourier transform to real functions is linear ? Bo Jacoby 11:06, 11 October 2005 (UTC)

• No good revolutionary sits back and waits for the revolution to come. He creates it himself with vision and vigour. No, you are no enemy of mine, nor am I an enemy of yours. I enjoy your comments. I listen to your opinions with respect, and to your arguments with attention. To oppose an idea just because it is new notation and original research is the lamest argument in all history of science, and those who used it are mercifully forgotten, while their victims are honored: Hippasus, Galileo, Giordano Bruno ...

Bo, no one is opposing it because it is new. They are opposing it here because it is new. Please understand the difference. —Steven G. Johnson 16:38, 10 October 2005 (UTC)

Is 'new' the only objection you have left against it by now ? Have you really become positively enthusiastic about it ? Will you spread the word elsewhere ? Bo Jacoby 11:06, 11 October 2005 (UTC)

Bo - I agree with you completely. COMPLETELY. DO IT. If you need my help let me know, I'll help. But not here, this is the north pole, and the decisive battles of the revolution are being waged elsewhere. This is where we analyze and explain past, present, and maybe future revolutions, but no engagements should be fought here.

Thank you very much. I need all the help I can get. I dont think I need to do more writing myself, however. Refer this WP discussion to the authors of the books that uses non-involutary fourier transforms and write $e^{2\pi ix}$ instead of $1^{x}$. Bo Jacoby 11:06, 11 October 2005 (UTC)

• I love your idea of using 1 instead of g for the metric tensor. It is accordance with Occam. Go ahead and use it. I'm with you. Sharing an idea is implementing an idea. If it creates trouble somebody will be tell you. (The idea might have been used by Jean-Marie Souriau in his fine book Géométrie et Relativité, but I am not sure.) Bo Jacoby 10:27, 10 October 2005 (UTC)

If I ever write a refereed paper involving the metric tensor, I will use it and hope it catches on. If I ever speak to anyone who is interested, I will lobby them, and hope it catches on. But I won't try to get it into a Wikipedia article where it doesn't belong, at least not one that is nominally describing something as established as the DFT. PAR 22:45, 10 October 2005 (UTC)

I was wrong about Souriau using '1' for the metric tensor. He uses the vertical bar | with indexes in the lower right and the upper left, to indicate covariant and contravariant components of the basis vectors, les clefs matricielles. But he writes the inner product of two vectors without the letter g. He uses 1_E for the identity function on the set E, ( $1_{E}(x)=x,(x\in E)$ ), not as the indicator function of E, ($1_{E}(x)=[x\in E]$ using Iverson bracket). You may enjoy reading Souriau. Bo Jacoby 11:06, 11 October 2005 (UTC)

Redo unitary

I should practice what I preach, so I redid the unitary section to get rid of the primed indices. The problem is, I replaced it with primed vector symbols, and this is still not in conformity with previous use of capitals as transformed quantities. I want to emphasize with the notation as much as possible the idea of having a constant vector object, and its components are the only things that change, the DFT being simply a coordinate transformation. That was the idea of the primed coordinate indices rather than the primed vector symbols. However, to express the unitary stuff using capital letters would further obscure this idea. Is there any objection to changing the capital letters to primed letters in the rest of the article? PAR 15:56, 8 October 2005 (UTC)

Capital letters are more conventional, and are used in most of the other Fourier transform pages (other than the discrete transforms, sigh). They are easier to distinguish visually than primed letters. And, most importantly, the frequency domain is sufficiently distinct, in practice, from the time domain that I don't agree that we want to minimize the differences between the two representations. I would rather you changed to capitals in the unitary section. —Steven G. Johnson 16:25, 8 October 2005 (UTC)

For those who think of the Fourier transform as a time-frequency pair, yes, you want to emphasize the distinction. For those who think of it as a coordinate transformation between the momentum and space representations of a quantum wave function, you want to emphasize the lack of distinction. We should not favor the time-frequency POV. PAR 18:54, 8 October 2005 (UTC)

First of all, the discrete Fourier transform is not typically used for quantum wave functions, and the article should favor the contexts in which the DFT is typically used. Second, even in quantum mechanics your prime notation is not common either. (When talking about wave functions, the most common notation I've seen is $\psi$ and ${\tilde {\psi }}$ for distinguishing the position and momentum-space representations...or rather, in QM the most common representation is probably Dirac notation which is basis-independent, and then using <x|ψ> etc.) The fact that it is a linear unitary transformation is already emphasized enough; we don't need to add an unusual notation on top of that. —Steven G. Johnson 22:27, 8 October 2005 (UTC)'

' Ok, I'm focusing on the concept and not the particular calculation technique. You know that the study of invariants under linear transformations is fundamental in physics. Also, you know I agree we don't need any unsual notation. But Parsevals and Plancherel's theorems are just so much mathematical gobbledygook to a beginner, and I am trying to convey an intuitive understanding of these theorems. Will you help me do that ? PAR 23:30, 8 October 2005 (UTC)

Involutions 2

I separated the involutions from the tricks. Is the Hartley transformation really an involution ? Shouldn't the divisor '2' be under the square root sign ? Shouldn't the formula be found in the Discrete Hartley transform article ? Bo Jacoby 13:13, 13 October 2005 (UTC)

Yes. Yes. Already mentioned.—Steven G. Johnson

Dear friend. The Discrete Hartley transform says: Its main distinction from the DFT is that it transforms real inputs to real outputs, with no intrinsic involvement of complex numbers, in variance your statement: taking the real part is necessary to get the Hartley transform (even for the real inputs, the outputs of H(x) are complex). Please make up your mind. That the involution form is basically an aside; it does not merit its own section is your opinion, but not your decision. You know that the matter is controversial. Nobody prevents you from expressing your view based on your experience, nor should you prevent others from expressing their view based on their experience. My experience-based view is that this involution has the simpler algebraic properties. Please restore my edit and stop acting like a censor of the spanish inquisition. Bo Jacoby 08:56, 14 October 2005 (UTC)

H(x) is not the Hartley transform. Its real part is, for real inputs. (The imaginary part is the Hartley transform with a different sign convention.) Personal attacks ala the Inquisition aside (nobody expects the Spanish Inquisition!), anything more than an aside is inappropriate because promotion of your personal non-standard DFT variant, whatever its merits, is original research, as has been repeatedly explained to you. If you prefer, we can delete mention of it entirely. —Steven G. Johnson 15:19, 14 October 2005 (UTC)

You claimed that the notation $1^{x}$ is considered 'original research' and I didn't pursue it. The involutary fourier transform was accepted by you. Nobody called it 'original research' until now. I just changed the division into sections. I trusted PAR that you would not remove my edits, but you did. Spanish Inquisition refer to your actions, not to your person. You remove anything that you personally don't like, as herecy. This is getting ridiculous. I must give up my attempt to clean up your messy article on discrete fourier transform, because you are working against it. Yes, you may delete it entirely. You are on your own. Good bye. Bo Jacoby 11:26, 17 October 2005 (UTC)

Bo - NO - I need help when I'm right and Steven J. is wrong. Its just that he's more or less right on this. PAR 14:50, 17 October 2005 (UTC)

Periodicity and aliasing

What does this have to do with the DFT? Aliasing is caused by periodic sampling. We don't need a DFT to see that $\cos(2\pi kn/N)\,$ and $\cos(2\pi k(n+N)/N)\,$ are indistinguishable. --Bob K 04:14, 13 December 2005 (UTC)

Yes, aliasing is caused by discrete sampling. And discrete sampling is part and parcel of the DFT as it is usually applied, and is part of what makes it distinct from the continuous Fourier transform. Yes, it's equally true for the DTFT (where it should also be mentioned), but in this case it's true for both forwards and inverse transforms. What exactly is your objection? —Steven G. Johnson

My objection is that I don't really know what you are trying to say that is actually useful information about the DFT. I have a feeling that there is a much better way to say it. I would like to help, but first I have to figure out what the point is. --Bob K 07:50, 13 December 2005 (UTC)

What purpose is served by the word finite in the sentence?: "and it means that in a finite discrete signal one cannot distinguish between frequencies j that differ by n". --Bob K 04:14, 13 December 2005 (UTC)

You're right, that should be removed. —Steven G. Johnson

What is the point of this?: "If one simply evaluates the DFT formula at $j+n\,$ then one finds that $f_{j+n}=f_{j}\,$,"   I.e., it appears that we are assuming the $x_{k}\,$ sequence is periodic in order to "prove" that the DFT thinks it is periodic. --Bob K 04:14, 13 December 2005 (UTC)

The effective periodicity of x is not used in this statement, so I don't know what you are referring to. —Steven G. Johnson 06:25, 13 December 2005 (UTC)

OK, I see that now. (I'm not used to your choice of symbols.) All you are saying is that the DFT is periodic in frequency. But the conclusion is that: "in a discrete signal one cannot distinguish between frequencies j that differ by n", which is true, but it isn't what you seem to have proved. You've at least skipped a step, haven't you? Furthermore, wouldn't it be simpler to just define: $y_{k}=x_{k}\cdot e^{{\frac {2\pi i}{n}}nk}\,$   (whose frequencies all differ from x by n). And then it is trivial to see that y = x. It has nothing to do with the DFT. --Bob K 07:50, 13 December 2005 (UTC)

Hi Bob, your basic issue seems to be that aliasing "has nothing to do with the DFT". Although aliasing can also be derived in other circumstances and in other ways, I can't agree with you entirely. Aliasing is still implicit in the definition of the DFT, and the implied periodicities are an intrinsic consideration in almost any application of the transform; it would be remiss not to mention it here.

I don't think you can avoid using the DFT definition in deriving the aliasing in this case, moreover, because the DFT definition defines what you mean by "samples" and "frequency" in this context. Because this corresponds to the usual definition for uniformly spaced samples, you don't even think about it, but it is there. For example, you could certainly apply the DFT to a sequence of numbers corresponding to non-uniformly spaced samples of some signal — the resulting DFT would not correspond to amplitudes of "frequencies" of the original signal in the usual sense, but would still have an aliasing property of a different sort. In general, the aliasing property can arise in contexts that have nothing to do with signals and sampling, e.g. many FFT algorithms exploit the implicit periodicity. Abstractly, there is also a close relation between the DFT and representation theory for the irreducible representations of the cyclic group (which would be a nice connection to mention in the article, although currently the representation theory articles in Wikipedia are painful to read).

You can quibble about the precise way in which the property is proved, I suppose, but any sufficiently short and clear proof seems fine to me. I'm not sure where you think the current article skips a step. —Steven G. Johnson 17:25, 13 December 2005 (UTC)

What you actually show is that the DFT of x has period n. And what the conclusion says (paraphrased) is: "If y is another signal whose frequencies differ (by n) from those of x, then one cannot distinguish the DFT of y from the DFT of x. (And therefore one cannot distinguish y from x.)" I am suggesting that we actually say those things, rather than trust them to the readers' intelligence. Moreover, when we do say them, we realize that the condition: "y is another signal whose frequencies differ (by n) from those of x" means simply this: $y_{k}=x_{k}\cdot e^{{\frac {2\pi i}{n}}nk}=x_{k}\,$. If you must talk about aliasing, then I suggest you at least make it clearer that it is not caused by the DFT, does not depend on the DFT in any way. My sensitivity probably stems from the misconceptions in the spectral leakage (stub) article (before I just re-wrote it). --Bob K 20:01, 13 December 2005 (UTC)

This discussion is conflating a statement and its converse; can we please be more precise? I think we can both agree that aliasing does not imply the DFT — aliasing can occur whenever you sample a signal. But it seems that you are also insisting upon the converse, with which I do not agree — you seem to also be saying that the DFT does not imply aliasing. —Steven G. Johnson 06:48, 14 December 2005 (UTC)

What I am trying to say, precisely, is that I think many people will get another misconception about the DFT. That misconception is that the DFT causes aliasing, regardless of what the article actually says. I am not asking you to retract your treatment. All I am now suggesting is that you explicitly refute that potential misconception. It can't hurt, and it will probably help somebody. --Bob K 21:55, 14 December 2005 (UTC)

You aren't making any sense to me. If the DFT implies aliasing, which you seem not to contest, then in that sense the DFT causes aliasing...but the latter statement you call a "misconception." Note that this is not the same thing as saying that the DFT is the sole context in which aliasing phenomena occur—you still seem to be confusing a statement with its converse. —Steven G. Johnson 23:14, 14 December 2005 (UTC)

I don't think I really care if the DFT implies aliasing or not. But maybe you will enjoy thinking about a signal defined this way:

$x(k)=\sum _{m=-\infty }^{\infty }w(k)e^{2\pi i(f+m)k}\,$,

I.e., the spectrum is periodic, by definition. So the periodicity of the DFT does not imply aliasing in that case. (Just a thought.) --Bob K 21:55, 14 December 2005 (UTC)

This equation makes no sense. Did you mean w(m) instead of w(k)? (It looks more like a Fourier series; the w(m) amplitudes are only uniquely determined if k is a continuous periodic coordinate.) What point are you trying to make? —Steven G. Johnson 23:14, 14 December 2005 (UTC)

w(k) is just about anything you wish. What I actually had in mind was some sort of finite window function. Its spectrum gets mixed (heterodyned) up to frequency f and periodically extended thereafter. Of course that doesn't make it look any different than before. But the point is that I defined it to comprise all the components that you would normally infer are aliases. Since they are defined as part of the signal to begin with, they aren't aliases. In that case, the periodicity of the DFT merely implies that the original, defined input was discrete to begin with. (A trivial point, but perhaps not to a mathematician.) --Bob K 00:50, 15 December 2005 (UTC)

I can't really agree with your interpretation here. The only case in which you can say for certain whether there is "really" aliasing is when you are sampling a continuous signal and you know the spectrum of the continuous signal and whether it is sufficiently bandlimited. If you start with a discrete signal there is an inherent ambiguity. —Steven G. Johnson 01:38, 15 December 2005 (UTC)

When you start with a discrete signal, aliasing is either undefined (because there was never any "true" frequency to begin with [as you just said]) or impossible (because all the frequency components are already periodically extended). In either case, ambiguous does not seem to be the right description, because it implies that you started with a continuous signal. --Bob K 02:09, 15 December 2005 (UTC)

Would you be happy if the article stated something like, "More generally, aliasing phenomena also occur whenever one is analyzing the frequency components of a discrete signal (or discrete samples of a continuous signal), such as in the discrete-time Fourier transform." I have no problem with this. —Steven G. Johnson 23:14, 14 December 2005 (UTC)

Not really (sorry), but thank you. Let's just leave it and move on. There are much bigger and easier fish to fry. --Bob K 00:50, 15 December 2005 (UTC)

"stacked" fractions in superscripts?

I like the stacked version better than the unstacked version. IMO, that's the whole point of having a cool math editor. --Bob K 21:11, 15 December 2005 (UTC)

Me too, but I don't have strong enough feelings about it to go through and change it. Knock yourself out if you want, but first you might ask User:Michael Hardy to explain his reasoning on this edit. —Steven G. Johnson 21:23, 15 December 2005 (UTC)

A major point of having a cool math editor is versatility: you can make it do what you want it to. "Stacked" is appropriate in some cases, but seldom within superscripts. Bob K, did you think I was saying "stacked" should never be used? If so, go back and read what I wrote, since you missed it entirely. Michael Hardy 21:53, 15 December 2005 (UTC)

PS: I'm betting you two will get outvoted on this one if it comes to that. Michael Hardy 21:53, 15 December 2005 (UTC)

Stacked notation does not work well for inline formulae. Using stacked for display and unstacked for inline places an extra burden on the reader. For a fraction with both numerator and denominator complicated, stacked display can be a great help to clarity; here, the benefit seems small. Outside of TeX, k/n can be marked up to appear as ^k⁄_n; but that's of little help in this case, partly because of Wikipedia's LaTeX limitations. Finally, stacking causes shrinking in an already-small superscript, cancelling some of the benefit of stacking in general. --KSmrq^T 01:57, 16 December 2005 (UTC)

So is this the voting process? How does everyone else know that it's happening? When is it over? --Bob K 02:18, 16 December 2005 (UTC)

Michael, in general I agree with you about stacking in superscripts. However, in this particular case, the stacking serves a useful purpose: to clearly separate the 2πi/n from the jk index product. If you don't do this, the ijk is somewhat confusing because all of the letters look similar. —Steven G. Johnson 04:31, 16 December 2005 (UTC)

Quite true. But I have to point out that my preferred (linear) notation is: $e^{j2\pi kn/N}\,$ ${\Big (}$or $e^{i2\pi kn/N}\,$, if you insist${\Big )}$, and I never have the problem you are worried about. I just think stacking looks great, compared to all the ugly computer code that has passed before my eyes. --Bob K 06:02, 16 December 2005 (UTC)

That is an improvement. But it still is clearer, I think, to keep the 2πi/n as a single unit (since mathematically most of the important properties of the DFT follow from the fact that it is a root of unity to the jk-th power). I also agree that it looks nicer stacked in this particular case. I'm changing it back. —Steven G. Johnson 20:07, 16 December 2005 (UTC)

we should change notation from subscripts to index in brackets.

hi guys, i've only recently started taking an interest in all of the Fourier/Laplace/Z transform pages and had no idea that there was such recent activity on this one.

i want to suggest something (that i am willing to do the grunt work) that i feel really strongly about. while the Laplace Transform, Fourier transform, Continuous Fourier transform, and Fourier series articles will have much broader interest and readership, i really believe that the discrete-time transforms, DTFT, DFT, Z, have much more narrow interest and constituency. while i do not claim that only electrical engineers doing signal processing are the only persons interested in or using these concepts, techniques, or algorithms, i do believe that it is principally people doing signal processing having such an interest. in that there is already a widely accepted notational convention for these discrete-time or discrete-frequency signals (that is $x[n]\$ and $X[k]\$) in the textbooks (i still consider Oppenheim and Schafer Discrete-Time Signal Processing to be the standard, but i s'pose we could argue about that) and lit, i really believe that we should adhere to that convention here. there are some of us agitating to revamp a bunch of EE electronics, control systems, communications systems, filtering, and general signal processing articles and we really should have notational consistency, and i really think that all of the discrete-time linear transforms (DTFT, DFT, Z) fall mostly in the EE and signal processing discipline.

may i change that notational convention from $x_{n}\$ to $x[n]\$ and $X_{k}\$ to $X[k]\$ (spending some considerable time) without someone reverting all of my effort away? FYI, there are two reasons i know of for why the EE discipline and lit has changed the notation. the main reason is that it is not uncommon to be processing a signal vector. in continuous time it looks like $\mathbf {x} (t)\$ and, if sampled it would be $\mathbf {x} [n]\equiv \mathbf {x} (nT)\$. but, if we need to refer to the individual components of the signal vector, it would be $x_{m}(t)\$ and $x_{m}[n]\$. do you see how it gets ugly if we have to say $x_{mn}\$ instead? also $x_{n}\$ is harder to do by hand than $x[n]\$. r b-j 02:59, 16 December 2005 (UTC)

It takes a brave soul to open that can of worms. I salute you. If wikipedia could achieve a standard notation, it would probably be a first. The world would beat a path to your door. I'm all for it, not so much for myself, because I have had sufficient time (about 4 decades) to get used to translating different notations. But I still recall the difficulties of trying to deal with that while trying to grasp the actual important concepts for the first time. It was frustrating, to say the least. I'm sure everyone can agree on that. But the sticking point is always getting consensus on a standard (as you clearly know). I think you have made a good case for Oppenheim and Schafer Discrete-Time Signal Processing. I support you, thank you, and wish you the best of luck, because you will probably need all of it. --Bob K 03:28, 16 December 2005 (UTC)

well, thanks. you clearly see almost precisely what my concern is. i'm used to opening these kind of cans (i've had long extended debates with Cleve Moler on comp.soft-sys.matlab about MATLAB's inability to have indices below 1, like 0 for the DFT), but i seldom "win" (the best argument doesn't always win, sometimes it matters who you are rather than the strength of what what you know or say). we'll see what others say, but this whole notational inconsistency is already a little ugly and will only get worse if it isn't fixed soon. r b-j 03:40, 16 December 2005 (UTC)

Let me guess... old Cleve celebrated the end of the 2nd millennium 1-Jan-2001, and he used to be a FORTRAN programmer. Been there, done that. But I got over it!! After growing to love C (which took about 5 minutes), it was very disappointing to discover FORTRAN's influence on Matlab. However, I have pretty much gotten used to it again. Some people crusade for right vs. wrong (bless your hearts), and others (like Cleve) stubbornly cling to whatever idea they heard first, and some of us just try to be the blades of grass that bend whichever way the wind blows. --Bob K 04:02, 16 December 2005 (UTC)

FYI (in case you didn't know), old Cleve is the primary designer of MATLAB and VP and cofounder of The Math Works. so he has other stubborn reasons (like he just can admit that they screwed up so badly not allowing the base indices to be adjustable). but also, for the sake of the product, you'ld think he'd be open-minded enough to want to see improvements, even if there would be a sorta "paradigm shift" in it. r b-j 21:59, 16 December 2005 (UTC)

The DFT is used by a wide audience, and so it is important to use as universal a notation as possible. If you use subscripts, everyone knows what you mean, but I think brackets are a bit too overloaded as far as notation goes. The Wikipedia articles aren't using a vector signal so that argument is moot. (I admit I don't have terribly strong feelings about this. I'll point out, however, that most of the literature on FFT algorithms uses subscripts as far as I can tell.) Moreover, you'll have to change literally dozens of Wikipedia articles that use the subscript notation. —Steven G. Johnson 04:38, 16 December 2005 (UTC)

Actually, I would like to see a lot more use of $x(nT)\,$ in a learning environment like this is supposed to be. And since $x[n]\,$ is a step closer to it than is $x_{n}\,$, that's another point in its favor (IMO). The literature you refer to is not written on an undergrad level. Are we trying to emulate grad school here? Maybe we should be trying for a consensus on that, because without it, we surely won't agree on much of anything else.

Have to say I am not swayed by the argument that brackets are more overloaded than subscripts... seen too much subscript abuse to accept that. (But it's you viewpoint, and you are entitled to it.)

Also think it's a bit short-sighted to argue that vectors won't be needed in the future, because they aren't needed now.

If the miracle occurs, and a consensus is reached, I don't think anyone would consider the effort required a good enough reason not to go forward. It could be done incrementally, over time. Or N volunteers could each take on 1 article. I would volunteer for that. And then there is the amazing Michael Hardy... apparently a human editing machine.

But I'm wasting my breath keystrokes, and I'm old enough to know better.

--Bob K 05:40, 16 December 2005 (UTC)

You definitely shouldn't use $x(nT)\,$ in most places, because that imposes a particular interpretation of the DFT as discrete samples of a putative function over a real domain. The DFT itself "knows" nothing about such interpretations, so we shouldn't imply that they are intrinsic, nor is this interpretation used for all applications. (It's fine to mention this under applications or whatever.) —Steven G. Johnson 18:22, 16 December 2005 (UTC)

i kinda agree with Steven about that. $x(nT)\,$ should exist only in the Sampling Theorem and related/supporting articles. but we should stick to the convention that if it surrounded by parenths, the argument is continuous. if an argument is surrounded by brackets, it is discrete. r b-j 21:59, 16 December 2005 (UTC)

I'm opposed to $x[n]\$ notation. I can't imagine how anyone could say $x[n]\$ is easier to write than $x_{n}\$ or how $x_{mn}\$ is uglier than $x_{m}[n]\$. Also the statement "all of the discrete-time linear transforms (DTFT, DFT, Z) fall mostly in the EE and signal processing discipline" is offensive, narrow-minded blindness. What is it about EE types that make them think they are the center of the universe? The only point in favor is Oppenheim and Schafer, which is a standard in my mind as well, but its not the bible. PAR 18:48, 16 December 2005 (UTC)

oh, c'mon PAR! when you see $x_{m}[n]\$ or $X_{m}[k]\$, you know which index is "time" or "frequency" and which index is the component number of the signal vector. when you see $x_{mn}\$ or $X_{mk}\$, it's not quite so obvious, is it? in fact, it looks like m and n are sorta the same kinda species of animal. if you had a vector of continuous-time functions, you wouldn't call the components "$x_{mt}\$", would you? wouldn't we say $x_{m}(t)\$? when sampling that function and converting the notation to continuous time, we need to have a change of notation to indicate that n is discrete while t is continuous and the brackets, if faithfully adhered to, really do that job nicely, yet they do not change the qualitative nature of the subscripts for the times we need subscripts.

You say "when you see $x_{m}[n]\$ or $X_{m}[k]\$, you know which index is "time" or "frequency" and which index is the component number of the signal vector." In fact I don't. You assume (as all EE's do) that I cannot possibly be using the DFT for anything but time analysis of a signal. In fact I use it as a digital approximation to a continuous Fourier transform when solving physics problems. What you call a discrete time index, I call the component of a vector! So when you mention "signal vector" I really don't know, from my point of view, which is the time index and which is the signal component. Only by looking at what you have been saying previously am I able to guess that m is probably the component number of the signal vector, and k is the component number of something I am used to calling a vector, you are not. You really, really have to stop assuming that EE's are the only people in the world who use discrete transforms. Any discipline which uses a continuous transform (e.g. physics as in quantum mechanics, heat transfer, etc.) will likely use a discrete transform as a calculational tool to calculate the continuous transform. Take the blinders off, please.

The bottom line is, we should follow the literature, rather than arguing about this. If there is multiple notations in the literature, then we will want one that is least restrictive, least specific to a particular discipline. If thats the EE notation, then so be it, but can we agree on how to solve the disagreement? PAR 23:56, 16 December 2005 (UTC)

whether the n in x[n] is "time" or "position", say on a photograph (then it would be x[n,m] for row and column (not necessarily respectively), or the independent variable of a p.d.f. (and DFTing would get you the characteristic function), or some other completely different physical quantity and you're breaking this thing up into a spectrum, it doesn't matter what you call it. the point is, if you have one of them, it's x[n]. if you have a few (or many) of them, it's the same x[n] but you subscript it (x_m[n]) then you have something to differentiate which one of the many. i do not assume that you "cannot possibly be using the DFT for anything but time analysis of a signal". doesn't matter if it's "time" or something else, it is the independent variable that is also the argument to the sinusoidal (or complex exponential) basis functions. doesn't have to be physical "time". r b-j 03:23, 17 December 2005 (UTC)

in terms of writing by hand, having to write tiny characters legibly is, for most people i know, harder to do than to write moderately-sized characters. the same is true for the prof at the blackboard. the s$x[n]\$ is far easier to write than $x_{n}\$, even if, on the blackboard (or whiteboard) the subscript is not miniature like on paper. r b-j 21:59, 16 December 2005 (UTC)

I would also say that it is not so much a matter of which one is easier to write or to type, but rather, which one is easier to read or to interpret. I am not so worried about the authors and the editors, I am more concerned about the readers and making sure that they can understand what is going on. In that sense, the bracket notation is much easier to understand when describing discrete-time signals, vectors, and matrices, than is the sub-script notation. -- Metacomet 22:53, 16 December 2005 (UTC)

I don't know if you realize, but $x[n]\,$ is by definition identical to $x_{n}\,$. It is purely an issue of notation, not of meaning. I think artices dealing with the DTFT, the DFT, and the ZT should use the bracketed notation rather than the subscript notation, for all of the reasons mentioned above. It does not need to create any confusion if you simply note, near the beginning of each article, that the article will be using the convention that

$x[n]\equiv x_{n}$

and then explain briefly the rationale (common convention in signal processing, indicative of vector/matrix notation, etc) for using this notation. It should not be a big deal for non-EE's to understand, and it would be a big help for EE's. Why are non-EE's so afraid of trying something different? There are good reasons why EE's have chosen these newer conventions, and they actually can help in other disciplines as well. It's helpful if you drop the not invented here paradigm. -- Metacomet 22:06, 16 December 2005 (UTC)

Why are EE's so afraid of trying something different? Why don't EE's realize that this is purely a matter of notation? Seriously, Metacomet, the condescension is coming a bit thick... —Steven G. Johnson 22:53, 16 December 2005 (UTC)

Steven -- I aplologize if I came across as condescending. I will try to be more respectful of other people in the future. -- Metacomet 03:11, 17 December 2005 (UTC)

One other point: I believe that the bracketed notation is actually older than the subscript notation. Back in the old days, before WYSIWIG computers, people used to use typewriters or text-based computers. Yes, I know it is hard to believe, but these antique devices did not provide the capability of creating sub-scripts or super-scripts the way we can today in our modern word processing applications or with LaTeX. So the way that people used to indicate sub-scripts was to place the sub-scripted character inside of square brackets, as in, $x[n]\,$ for a one-dimensional vector or even $A[m,n]\,$ for a two-dimensional matrix.

That's an interesting theory, but you should be a bit more cautious about speculation. I have an 1866 re-printing of Gauss' 1805 notebook, in Latin, which describes what is perhaps the first realization of the full sine+cosine DFT (and an FFT), for trigonometric interpolation of real data. He uses superscripts ("si termini ultimi in X statuuntur $\alpha ^{m}\cos mx+\zeta ^{m}\sin mx$" etc.). You're perhaps forgetting that even before typewriters came paper and pencil, and blackboards, and mathematicians are notoriously lazy — in my opinion (r-b-j notwithstanding) subscripts are quicker to write than bracketed indices (higher chalk/math ratio!). (By the way, in 1866 they apparently had no trouble typesetting equations, and my understanding is that sub/superscripts were common on technical typewriters.) —Steven G. Johnson 22:53, 16 December 2005 (UTC)

It's only half-speculative, because I am pretty sure about it. And I preceded my comments with the words "I believe that...". -- Metacomet 00:25, 17 December 2005 (UTC)

I never said that subscripts and superscripts were not also used. Obviously, in handwriting or typesetting, or with an advanced enough typewriter, you can do subscripts. What I did say was that brackets were also used, when you had a typewriter that could not handle subscripts, and people had no trouble understanding what they meant. -- Metacomet 00:23, 17 December 2005 (UTC)

By the way, like all right-thinking folk, Gauss uses i as the "quantitas imaginaria", not this goofy j. Although he also uses capital E for the "basis logarithmorum naturalium", I have to admit. =) —Steven G. Johnson

What's goofy is that it is called the "imaginary unit". I don't know what a better name would be, but it is anything but "imaginary". -- Metacomet 00:28, 17 December 2005 (UTC)

Let's call it Johnson, so maybe Steve won't mind the $j\,$ notation. --Bob K 01:40, 17 December 2005 (UTC)

Or since it stands for the vector [0,1], we could use this symbol: $\uparrow$   --Bob K 01:40, 17 December 2005 (UTC)

i actally agree with the semantic of calling it the "imaginary unit" and calling (real) multiples of it "imaginary numbers". i think we can come up with real physical quantities legitimately quantified as "negative", but there are no real numbers that when you square them, become negative. only numbers we "imagine". r b-j 03:23, 17 December 2005 (UTC)

I am not suggesting that we should abandon WYSIWIG and go back to using square brackets in all situations. What I am saying, however, is that this convention existed long before EE's adopted it as notation for describing discrete-time signals, and I believe that it is a perfectly acceptable convention for vector and matrix notation. -- Metacomet 22:20, 16 December 2005 (UTC)

The question is not whether it is acceptable, it is whether it is preferable to the extent of a mass conversion. (If there is a mass conversion, please also change k to the frequency index, n to the input index, and N to the size of the transform. The current labels drive me crazy.) —Steven G. Johnson 22:53, 16 December 2005 (UTC)

That would be awesome. --Bob K 23:58, 16 December 2005 (UTC)

yeah! once i felt safe enough to attack this thing without getting my work reverted, that goes without saying. my intention, as much as possible, is to implement the notational convention as i see it in Oppenhiem & Schafer as well as other texts and common in the IEEE lit (not all IEEE papers use it). anyway, i most certainly would make those changes, Steven. r b-j 03:23, 17 December 2005 (UTC)

I agree 100 percent on your notation changes. We should not use i or j as index variables, since either one can represent the imaginary unit. -- Metacomet 00:15, 17 December 2005 (UTC)

As far as a mass conversion is concerned, I would say that we should only change articles where it makes sense to do so (not to state the obvious) – mainly articles related to discrete-time signals, discrete-time systems, discrete transforms, and image processing. -- Metacomet 00:15, 17 December 2005 (UTC)

that was my original proposal and intent. r b-j 03:23, 17 December 2005 (UTC)

Need to find common ground

Okay, I am sorry for getting in the middle of this discussion. I lost my head for a while. It is very difficult to get a consensus with such a diverse group of people coming from so many different points of view.

I just took another look at the article itself, and regardless of where you stand on the issue of brackets versus subscripts, it is really clear that the current notation in the article is really problematic. Again, I cannot speak for everyone, but it seems to me that no one should be happy with the current situation.

So if my assumption is correct, then maybe we shoud see if we can find at least some common ground.

I would make the following recommentaions:

• Replace the symbol $n\,$ with $N\,$ representing the number of elements in the input data vector and the transformed data vector.

• Use the letter $i$ to represent the imaginary unit. Obviously, most EE's (myself included) would prefer to use $j$, but the rest of the world uses $i$, and I know I can live with either one, as long as it is consistent.

• Do not use the letter $j\,$ as an index variable in either the base domain or the transform domain. I know that this issue does not concern non-EE's, but I think you can understand how it is a major problem for EE's.

• Use any or all of the following lower case letters as index variables: $m,n,p,q,k\,.$ That is five different options, which should be plenty. If not, we can always turn to the Greek alphabet for more.

Can we all agree on at least these initial steps to help move forward? Please comment.

-- Metacomet 03:28, 17 December 2005 (UTC)

i agree (and meant to say that - it was not my intention to change i to j here) and your suggestion not to use j as an index (for the sake of EEs) is a good idea. i never thought of p and q as integer types (my 35 year old Fortran influence) but they look good. i don't know that we'll need them. we'll see.

it is my intention to make such a notational change, including brackets, to this article (without changing the math or concepts) and see how far it flies. if someone want to disuade me, please do it now before i put some time into it. Steven, if this flies, i would like to extend this convention to the FFT and other related articles (you mentioned that there are at least a dozen). we'll keep i to some depth, but the closer we get to the EE domain, at some point that i is gonna become j. after this sticks, then i'm gonna attack LTI system theory and the Sampling theorem articles. but i feel like "what's the point" if some of the basis articles have such different notational convention that a neophyte might not connect them. r b-j 03:41, 17 December 2005 (UTC)

Even though I agree with changing from subscript to brackets, I would recommend that you hold off on that idea for now. If we can get consensus on the few items I listed above, and the one item I listed below, then maybe we can at least accomplish something in the short run.

In the meantime, we can continue to discuss the subscripts versus brackets issue and maybe try to find a solution. -- Metacomet 03:46, 17 December 2005 (UTC)

Another recommendation:

• Do not use the letters f or F to represent functions, vectors, or matrices in the context of a discussion of the Fourier transform. It is very common to use ${\mathcal {F}}$ as an operator to represent the Fourier transform itself. It gets very confusing to talk about the F of f as in ${\mathcal {F}}\{f_{k}\}$ as to which is the vector and which is the operator....

-- Metacomet 03:44, 17 December 2005 (UTC)

meta, i'm doing that and i'm moving the i to the front (and the 2 π right after the i and nk in the top of the fraction and N in the bottom). i'm dealing with that right now. please hold off for about another hour. oh, and f becomes X. r b-j 04:31, 17 December 2005 (UTC)

I just wanted to give a few things a bit of a test drive. There is no harm done, things can always be reverted if they don't work out. I will leave it alone for now though. I am going to sleep now anyway. I will take a look at it tomorrow. Good luck.

In addition to the changes you just mentioned, I would replace j with m and leave k alone for now. Or use n and k if you want to do the extra work. -- Metacomet 04:45, 17 December 2005 (UTC)

Actually, I do not agree with putting the nk on top of the fraction. Believe it or not, I think it makes sense to put the i in front of the fraction, the 2 π on top of N for the fraction, and then the nk after the fraction. The reason is that you can attach in important interpretation to the 2 π/N as representing the discrete angular frequency increment (in radians per sample) that is very useful in understanding the DFT and more importantly, in implementing the frequency domain in a computer simulation. If you don't know what I mean, I will try to explain later. It's a bit complicated. -- Metacomet 04:49, 17 December 2005 (UTC)

Using k as the frequency index and n as the input index seems vastly more standard to me than the current indexing. If you're going to change the indices, please change all three ($j,k,n\rightarrow k,n,N$). Note that there are literally dozens of articles to change. See Category:Digital signal processing and Category:FFT algorithms and Category:Fourier analysis. However, I think it was a bad idea to start making changes before there is a clear consensus on exactly what changes to make. 24.61.43.18 05:25, 17 December 2005 (UTC)