DFT 后条目的顺序发生了变化

Question

我试图了解离散傅里叶变换（DFT）是如何工作的。我生成一些数据

 n<-5
 set.seed(100)
 x<-rnorm(n)

以及我用来计算 DFT 的正交矩阵

 omega<-exp(-2*pi*1i/n)
 E<-n^(-1/2)*omega^(0:(n-1)*matrix(0:(n-1),n,n,byrow=TRUE))
 round(Re(crossprod(E,Conj(E))),15)

DFT 由下式给出

 x%*%t(E)

确实，我们可以检查这与

fft

给出的结果一致

 round(n^(-1/2)*fft(x),10)==round(x%*%t(E),10)

现在我应该能够使用

恢复

x

 Re(colSums(c(x%*%t(E))*E))

但这给出了

[1] -0.50219235 0.11697127 0.88678481 -0.07891709 0.13153117

而

x

等于

[1] -0.50219235 0.13153117 -0.07891709 0.88678481 0.11697127

所以我恢复了

x

，但条目的顺序发生了变化。第一个条目仍然是第一个条目，但其他条目混合在一起。谁能解释为什么会发生这种情况或者我做错了什么？

非常感谢任何帮助！

Answer 1

DFT 矩阵不是正交的，因此矩阵的转置不等于逆矩阵。因此，您不会通过乘以矩阵的转置来撤消运算。

由于矩阵是对称的并且转置是相同的，所以你所做的就是将向量乘以矩阵的平方。该矩阵的平方确实是正交的，因此起到坐标平移的作用（即条目的顺序发生了变化）。

round( Re( E %*% E ), 10)
##      [,1] [,2] [,3] [,4] [,5]
## [1,]    1    0    0    0    0
## [2,]    0    0    0    0    1
## [3,]    0    0    0    1    0
## [4,]    0    0    1    0    0
## [5,]    0    1    0    0    0

该矩阵是对称且正交的，因此等于其自身的转置及其逆。

您的代码和设置正确；为了确认这种情况，您可以使用内置的快速傅里叶变换函数

fft

Re(fft(fft(1:10)))/10
##  [1]  1 10  9  8  7  6  5  4  3  2

当对一组数字使用两次时，它也会以相同的方式改变顺序。