DFT 作为基变换

离散傅里叶变换听起来很分析，但其核心不过是一次基变换。它把一个信号从标准基（每个时间采样一个坐标）改写到傅里叶基（每个纯频率一个坐标）。还是同一个向量，只是新坐标揭示了信号含有多少各种振荡。

具体地，DFT 是乘以一个矩阵 F，其元素是单位根：F_jk = exp(-2 pi i j k / n)。按 1/sqrt(n) 缩放后该矩阵是酉的，F^* F = I，故变换是复空间中的一次旋转：它保持长度（帕塞瓦尔定理），并可由其共轭转置平凡地求逆。F 的列是傅里叶基向量，是相互正交的纯频率。

下面是把它与特征理论相系的妙处：傅里叶基同时对角化每一个循环矩阵（每行都是上一行循环移位的矩阵，即卷积的矩阵形式）。换言之，傅里叶向量是所有平移不变运算的共同特征向量，这正是卷积在频域里变成简单乘法的原因。

为何重要：单凭这一事实就驱动了快速滤波、音频与图像压缩，以及微分方程的谱方法，而这一切都因 FFT 而切实可行——它以 n log n 而非 n^2 的时间计算 F x。警示：DFT 假定信号周期，故突兀的边沿会让能量跨频率泄漏（频谱泄漏），通常用加窗来驯服。