Discrete Fourier Transform = Correlation?
-
- KVRian
- 1379 posts since 26 Apr, 2004 from UK
If you consider the DFT as a matrix multiplication and if you assume that the correction factor in the DFT/iDFT is the same in both (1/sqrt(nd samples), then the DFT could be interpreted as a change of basis (well, it actually is a change from the basis of dirac functions to the basis of sine/cosines) and as such rotations.
I would NOT consider DFT as a 2D rotation, it is a 2ND rotation, with N the number of samples.
I would NOT consider DFT as a 2D rotation, it is a 2ND rotation, with N the number of samples.
- KVRAF
- 7892 posts since 12 Feb, 2006 from Helsinki, Finland
https://en.wikipedia.org/wiki/DFT_matrix
also http://mathworld.wolfram.com/FourierMatrix.html (which shows you how to factorize the matrix to get FFT)
also http://mathworld.wolfram.com/FourierMatrix.html (which shows you how to factorize the matrix to get FFT)
-
- KVRian
- 1379 posts since 26 Apr, 2004 from UK
It's funny, it's a Vandermonde matrix
edit: didn't see it was mentioned on the wikipedia page.
edit: didn't see it was mentioned on the wikipedia page.
Last edited by Miles1981 on Thu Aug 25, 2016 8:13 pm, edited 1 time in total.
-
- KVRAF
- 2256 posts since 29 May, 2012
Notice that the rotated quantity is being added to the same frequency bin in a for loop. To me it just looks like a coincidence that the formulas look similar but maybe i'm wrong.
~stratum~
- KVRAF
- 12555 posts since 7 Dec, 2004
https://en.wikipedia.org/wiki/Linear_al ... _expansion
All you're doing by describing as "not rotation" is confusing people. People need to understand at its core it is a very simple rotation in linear algebra and you can add the complexity by saying "plus ..."
For example I don't describe a waffle as "not bread", I describe it as bread made with a particular recipe for the dough and cooked in a particular way. It's a "type of" bread.
This sort of abstraction is critical to actually understanding anything and it is absolutely awful that it isn't core to the way these things are taught.
All you're doing by describing as "not rotation" is confusing people. People need to understand at its core it is a very simple rotation in linear algebra and you can add the complexity by saying "plus ..."
For example I don't describe a waffle as "not bread", I describe it as bread made with a particular recipe for the dough and cooked in a particular way. It's a "type of" bread.
This sort of abstraction is critical to actually understanding anything and it is absolutely awful that it isn't core to the way these things are taught.
Free plug-ins for Windows, MacOS and Linux. Xhip Synthesizer v8.0 and Xhip Effects Bundle v6.7.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
-
- KVRAF
- 2256 posts since 29 May, 2012
You may be right but basically the problem is that i could not understand what sense it would make to add such rotated quantities together if dft wasnt something more than rotation.
~stratum~
- KVRAF
- 12555 posts since 7 Dec, 2004
How could I not note this? I just typed it from memory.stratum wrote:Notice that the rotated quantity is being added to the same frequency bin in a for loop. To me it just looks like a coincidence that the formulas look similar but maybe i'm wrong.
It is more than rotation, it's "rotation++".
Being more of something doesn't make it less of or not rotation to begin with.
It is a type of rotation.
Free plug-ins for Windows, MacOS and Linux. Xhip Synthesizer v8.0 and Xhip Effects Bundle v6.7.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
-
- KVRAF
- 2256 posts since 29 May, 2012
Ok, but that does not settle the issue any more than saying that rotation formula is a part of the dft formula, but that's not how i choose to understand things. Maybe thats why i am not a good math student. When something is not explained i reject to follow and that obviously makes me a rebel as a student and rebels to not pass their exams and go their own way (as a result).
~stratum~
- KVRAF
- 12555 posts since 7 Dec, 2004
There is no "rotation formula" or "Fourier formula" to discuss. This is just clouding the issue by throwing up meaningless terms like a box filled with foam packing beads. What we really want is the simple mechanism at play so we can understand how it works and at its core it is this: rotation. Dump all those foam beads out of the box and focus on what is in the box, not superfluous fluff.
Mostly packing fluff.
Mostly packing fluff.
Free plug-ins for Windows, MacOS and Linux. Xhip Synthesizer v8.0 and Xhip Effects Bundle v6.7.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
-
- KVRAF
- 2256 posts since 29 May, 2012
From my perspective it looks like this question needs to be handled the way the question if dft=correlation question was handled, not by simply claiming that a poor answer is just as good as any other. Oddly enough before i had posted the answer nobody had even tried to answer the question that had started the thread.
P.s.there are already too many bad math teachers who are the cause of this problem and for that reason linear algebra cannot be an high school subject as you claim.
P.s.there are already too many bad math teachers who are the cause of this problem and for that reason linear algebra cannot be an high school subject as you claim.
~stratum~
- KVRAF
- 12555 posts since 7 Dec, 2004
Linear algebra can't be a high-school subject? It is.
Free plug-ins for Windows, MacOS and Linux. Xhip Synthesizer v8.0 and Xhip Effects Bundle v6.7.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
-
- KVRAF
- 2256 posts since 29 May, 2012
A part of linear algebra is an high school subject. A tiny one. Tiny because that is the extent high school teachers can be relied upon to explain. Not because some of those kids could not understand more.
~stratum~
- KVRAF
- 12555 posts since 7 Dec, 2004
I don't agree. The vast majority of people have a lot of trouble understanding basic abstract concepts. A basic grasp is possible between one and two sigma with understanding well above two.
Blaming educators for what is in fact the result of the limited intellectual capacity of their students is disingenuous at best.
With no possibility of providing effective education to the masses in such a format while focusing on simple cost vs. benefit analysis and allowing the "free market" to determine curriculum, teachers with degrees in mathematics also become two-sigma (linear correlation) or likely even more rare.
Blaming educators for what is in fact the result of the limited intellectual capacity of their students is disingenuous at best.
With no possibility of providing effective education to the masses in such a format while focusing on simple cost vs. benefit analysis and allowing the "free market" to determine curriculum, teachers with degrees in mathematics also become two-sigma (linear correlation) or likely even more rare.
Free plug-ins for Windows, MacOS and Linux. Xhip Synthesizer v8.0 and Xhip Effects Bundle v6.7.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
The coder's credo: We believe our work is neither clever nor difficult; it is done because we thought it would be easy.
Work less; get more done.
-
- KVRAF
- 2256 posts since 29 May, 2012
The dft matrix article mystran had posted looks like an explanation in the sense that a number of correlation operations could be written as a matrix multiplication. The dft code itself isnt showing anything interesting as far as i can see. Somewhere above miles notes the change in basis, which could be of some use to relate the two. While a change in basis is already obvious, the way it could be interpreted as rotation and as to why that should be done other than that its just possible to do so does not look clear to me as corelation itself looks explanatory adequate. Maybe there is some substance to it. Thats a possibility.
~stratum~
-
- KVRAF
- 2256 posts since 29 May, 2012
Perhaps you have introduced the idea of rotation just to explain complex dft but i would say its just another algebraic ring in which integral transforms work the same way due to correlation and orthogonality. its just more general and symmetric therefore easier to use. Thats the way i see it. Perhaps somebody can explain if there is some meaning in the idea of rotation, i dont know. That could be interesting.
~stratum~