复数矩阵和快速傅里叶变换type
status
date
slug
summary
tags
category
icon
password
Property
复数矩阵
复数向量: ，向量的每一个分量都是复数
此时不再属于实向量空间，它现在处于复向量空间。
复向量的模
实向量计算模只需要计算 即可；而如果对复向量使用 ，则有
是复数，平方后虚部为负，求模时本应相加的运算变成了减法（如向量 ，右乘其转置后结果为 ，但此向量的长度显然不是零）
复向量求模应使用，即
向量共轭的转置乘以原向量（如向量 ，右乘其共轭转置后结果为 ）
把共轭转置乘以原向量记为 ， 读作埃尔米特（人名为Hermite，形容词为Hermitian）
复向量的内积
同理可得，对于复向量，内积不再是实向量的 形式，复向量内积应为
对称性
对于实矩阵， 即可表达矩阵的对称性。而对于复矩阵，同样需要求一次共轭
例如 是一个复数情况下的对称矩阵，这叫做埃尔米特矩阵，有性质 。
正交性
标准正交向量：，对于复向量需要求共轭：。
标准正交矩阵： 有 。对于复矩阵则有 。
就像人们给共轭转置起了个“埃尔米特”这个名字一样，正交性在复数情况下也有了新名字，酉，酉矩阵与正交矩阵类似，满足 的性质。傅里叶矩阵就是一个酉矩阵。
傅里叶矩阵
阶傅里叶矩阵
是一个非常特殊的值，满足 ，其公式为。易知 在复平面的单位圆上， 。
在傅里叶矩阵中，当计算 的幂时， 在单位圆上的角度翻倍。比如在阶情形下， ，即位于单位圆上 角处，其平方位于单位圆上 角处，而 位于处。从开方的角度看，它们是的 个六次方根，而一次的 称为原根。
阶傅里叶矩阵，先计算 有 ，
矩阵的四个列向量正交。不过 的列向量并不是标准的，可以给矩阵乘上系数 （除以列向量的长度）得到标准正交矩阵 。此时有，于是该矩阵的逆矩阵也就是其共轭转置 。
快速傅里叶变换（Fast Fourier transform/FFT）
对于傅里叶矩阵， 、 、 之间有着特殊的关系。
一般情况下，用一个列向量右乘 需要约 次计算，计算量是比较大的。我们想要减少计算量，于是要分解 ，联系到 ，有
- 第一个矩阵是修正矩阵
由单位矩阵和对角矩阵 组成，显然其计算量来自矩阵，对角矩阵的计算量约为即这个修正矩阵的计算量约为，单位矩阵的计算量忽略不计。
- 第二个矩阵是两个与零矩阵组成的，计算量约为
- 第三个矩阵通常记为矩阵，是一个置换矩阵，其作用是将前一个矩阵中的奇数列提到偶数列之前，将前一个矩阵从 变为 ，这个置换矩阵的计算量也可以忽略不计
所以复杂度的计算化简为 复杂度的计算。可以进一步化简 得到与 有关的式子 ：
的计算量进一步分解为 的计算量，如此递归下去最终得到含有一阶傅里叶矩阵的式子。
化简后计算量： ，约为 ，算法复杂度为 。
于是原来需要 的运算现在只需要 就可以实现了。不妨看看 的情况，不使用FFT时需要 次运算，使用FFT时只需要 次运算，运算量大约是原来的。