了解离散傅里叶变换
我有一个关于离散傅里叶变换的小疑问。 如果我理解正确的话，那么我们所做的就是将多项式转换为其点值表示形式，其中 n 个点表示多项式的 n-1 次方。 但为什么我们必须用 n 次单位根来评估它呢？ 难道没有任何其他 n 点唯一地标识这个多项式并且更简单吗？
I have a small query regarding the discrete Fourier transforms. If I understand correctly, then what we do is convert a polynomial to its point value representation, with n points for a polynomial that goes up to the power of n-1. But why must we evaluate it at the nth roots of unity? Wouldn't any other n points uniquely identify this polynomial AND be much simpler?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
两者都不是。 1) 不能保证 n 个任意点都有效，2) 它不会更简单。 换个角度问：你为什么反对统一的根源？
No to both. 1) There's no guarantee that n arbitrary points would work and 2) it wouldn't be simpler. Turn the question around: why do you object to the roots of unity?
主要的应用原因是
从直觉上讲，这些点都不具有随机点，因为它们不形成一个组。 还有更多的理论原因（还有一些更实用的原因）
The chief applicative reasons are
You'd have none of these with random points - intuitively speaking, because they do not form a group. There are many more theoretical reasons (and also a few more applicative ones)
不，不是真的。 它与多项式无关。
它是将向量（初始数字序列）分解为不同的向量
基础。 只是这个基具有一系列非常有用的属性：
（1）它是正交的——向量不会混合，并且确定变换回原始基是非常简单的。
(2) 傅里叶基向量是移位（或循环移位，对于离散情况）运算的特征向量——傅里叶
移动向量索引后的基函数仍然是相同的函数（乘以数字）。 这使得卷积和一大类微分方程的解在傅立叶空间中变得非常简单。
(3) 最后，条目是统一的根——这引发了FFT，这是迄今为止发现的最优雅的算法之一，减少了更改基础所需的 N^2 操作到 N log N。
No, not really. It's got nothing to do with polynomials.
It's about decomposing a vector (the initial sequence of numbers) into a different
basis. It's just that this basis has a series of very useful properties:
(1) It's orthogonal -- the vectors don't mix, and determining the transformation back to the original basis is exceedingly simple.
(2) The Fourier basis vectors are eigenvectors of the shift (or circular shift, for the discrete case) operation -- a Fourier
basis function, after shifting the vector indices, is still the same function (times a number). That's what makes convolutions and the solution of a large class of differential equations very simple in Fourier space.
(3) And finally, the entries are roots of unity -- this gives raise to the FFT, one of the most elegant algorithms ever discovered, reducing the N^2 operations required for a change of basis to N log N.
这是离散傅立叶变换的两个“直观”解释。 它们不会直接跳入方程式，而是以一种希望某人告诉我这个之前的方式引导您完成
http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/
http://www.altdevblogaday.com/2011/05/17/understanding-the-fourier-transform/
Here are two "intuitive" explanations of the Discrete Fourier Transform. They do not jump into equations directly, but walk you through in a wish-someone-told-me-this-before way
http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/
http://www.altdevblogaday.com/2011/05/17/understanding-the-fourier-transform/