在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

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