By Long Luo
傅里叶变换(Fourier Transform)是什么？ 傅里叶变换 ( Fourier Transform ) (\textit{Fourier Transform}) ( Fourier Transform ) ( Fourier Series ) (\textit{Fourier Series}) ( Fourier Series ) 最伟大的数学发现 之一。
傅里叶变换 ( Fourier Transform ) (\textit{Fourier Transform}) ( Fourier Transform ) 形象展示傅里叶变换 ，讲的非常好。
傅里叶级数和傅里叶变换背后的本质 : 任何函数 都可以写成正弦函数 之和。
如下Gif动图所示：
下面这个视频 12分钟的傅立叶级数动画 ，我们可以看到任何图像都可以用大圆套小圆来绘制。
因为我们日常看到的世间万物都会随时间流逝 而变化，比如一段声音，一幅图像或者一盏闪烁的交通灯，这种以时间作为参照来观察动态世界的方法我们称其为时域分析 。
傅里叶告诉我们任何一个信号都可以用 2 2 2
时域表达：自变量是时间或者空间的坐标，因变量是信号在该处的强度；
频域表达：把信号“展开”成不同频率的简单正弦函数的叠加，相当于看作是定义在所有频率所组成的空间（称为频域空间）上的函数，自变量是不同的频率，因变量是该频率所对应的简谐振动的幅度。
这两个函数一个定义在时域（或空域）上，一个定义在频域上。看起来的样子通常截然不同，但是它们是在以完全不同的方式殊途同归地描述着同一个信号。它们就象是两种不同的语言，乍一听完全不相干，但是其实可以精确地互相翻译。在数学上，这种翻译的过程被称为傅立叶变换 ( Fourier Transform ) (\textit{Fourier Transform}) ( Fourier Transform )
傅里叶变换(Fourier Transform)可以做什么？ 在傅立叶变换的所有这些数学性质中，最不寻常的是这样一种特性：一个在时域或空域上看起来很复杂的信号（譬如一段声音或者一幅图像）通常在频域上的表达会很简单。这里「简单」的意思是说作为频域上的函数，它只集中在很小一块区域内，而很大一部分数值都接近于零。例如下图是一张人脸和它对应的傅立叶变换，可以看出，所有的频域信号差不多都分布在中心周围，而大部分周边区域都是黑色的（即零）。
这是一个意味深长的事实，它说明一个在空域中看起来占满全空间的信号，从频域中看起来很可能只不过占用了极小一块区域，而大部分频率是被浪费了的。这就导出了一个极为有用的结论：一个看起来信息量很大的信号，其实可以只用少得多的数据来加以描述。只要对它先做傅立叶变换，然后只记录那些不接近零的频域信息就可以了，这样数据量就可以大大减少。
基本上，这正是今天大多数数据压缩 方法的基础思想。在互联网时代，大量的多媒体信息需要在尽量节省带宽和时间的前提下被传输，所以数据压缩从来都是最核心的问题之一。而今天几乎所有流行的数据压缩格式，无论是声音的mp3格式还是图像的jpg格式，都是利用傅立叶变换才得以发明的。从这个意义上说来，几乎全部现代信息社会都建立在傅立叶的理论的基础之上。
关于不确定性原理 ，可以看下这个讲解的视频：直观看待不确定性原理：不只是量子现象哦 。
背景知识 在学习快速傅里叶变换 ( FFT ) (\textit{FFT}) ( FFT )
复数(Complex Number) 复数 ( Complex Number ) (\textit{Complex Number}) ( Complex Number ) a + b i a+bi a + b i a a a ( Real part ) (\textit{Real part}) ( Real part ) b b b ( Imaginary part ) (\textit{Imaginary part}) ( Imaginary part ) i i i x 2 = − 1 x^2=-1 x 2 = − 1 − 1 \sqrt{-1} − 1 C \textit{C} C
复平面 ( Complex Plane ) (\textit{Complex Plane}) ( Complex Plane ) x-axis \textit{x-axis} x-axis y-axis \textit{y-axis} y-axis
每一个复数 a + b i a+bi a + b i ( a , b ) (a, b) ( a , b ) 0 0 0
复数的模 复数的模是指 z z z ∣ z ∣ \left| z \right| ∣ z ∣
那么对于复数 z = a + b i z=a+bi z = a + b i ∣ z ∣ = a 2 + b 2 \left| z \right|=\sqrt{a^2+b^2} ∣ z ∣ = a 2 + b 2
复数的幅角 复数的幅角 θ \theta θ z z z
z = a + b i = ∣ r ∣ × ( c o s θ + i ⋅ s i n θ ) z=a+bi=\left| r \right| \times (cos\theta+i \cdot sin\theta)
z = a + b i = ∣ r ∣ × ( c o s θ + i ⋅ s i n θ )
复数的大小 因为虚数 i i i 90 ° 90° 9 0 ° 虚数无法比较大小 。
复数之间的大小关系只存在等于 和不等于 两种关系，两个复数相等当且仅当实部虚部对应相等。
对于虚部为 0 0 0
复数的运算 复数之间的运算满足结合律，交换律和分配律。
复数之间的运算法则：
加法：满足平行四边形法则。
( a + b i ) + ( c + d i ) = ( a + c ) + ( b + d ) i (a+bi)+(c+di)=(a+c)+(b+d)i
( a + b i ) + ( c + d i ) = ( a + c ) + ( b + d ) i
减法：
( a + b i ) − ( c + d i ) = ( a − c ) + ( b − d ) i (a+bi)-(c+di)=(a-c)+(b-d)i
( a + b i ) − ( c + d i ) = ( a − c ) + ( b − d ) i
乘法：幅角相加，模长相乘。
( a + b i ) ⋅ ( c + d i ) = a c + a d i + b c i + b d i 2 = ( a c − b d ) + ( a d + c b ) i (a+bi)\cdot(c+di)=ac+adi+bci+bdi^2=(ac-bd)+(ad+cb)i
( a + b i ) ⋅ ( c + d i ) = a c + a d i + b c i + b d i 2 = ( a c − b d ) + ( a d + c b ) i
除法：
a + b i c + d i = ( a + b i ) ⋅ ( c − d i ) ( c + d i ) ⋅ ( c − d i ) = ( a c + b d ) + ( b c − a d ) i c 2 + d 2 = ( a c + b d ) c 2 + d 2 + ( b c − a d ) i c 2 + d 2 \frac{a+bi}{c+di} = \frac{(a+bi) \cdot (c-di)}{(c+di) \cdot (c-di)} = \frac{(ac+bd)+(bc-ad)i}{c^2+d^2} = \frac{(ac+bd)}{c^2+d^2} + \frac{(bc-ad)i}{c^2+d^2}
c + d i a + b i = ( c + d i ) ⋅ ( c − d i ) ( a + b i ) ⋅ ( c − d i ) = c 2 + d 2 ( a c + b d ) + ( b c − a d ) i = c 2 + d 2 ( a c + b d ) + c 2 + d 2 ( b c − a d ) i
共轭复数(Complex Conjugate) 对于一个复数 z = a + b i z=a+bi z = a + b i 共轭复数 为 z ′ = a − b i z^{'}=a-bi z ′ = a − b i z ′ z^{'} z ′ z z z complex conjugate \textit{complex conjugate} complex conjugate
共轭复数的性质：
z ⋅ z ′ = a 2 + b 2 z\cdot z^{'}=a^2+b^2 z ⋅ z ′ = a 2 + b 2
∣ z ∣ = ∣ z ′ ∣ \left| z \right| = \left| z^{'} \right| ∣ z ∣ = ∣ ∣ ∣ z ′ ∣ ∣ ∣
单位复根 数学上，数 x x x n n n r r r r n = x , n = 1 , 2 , 3 , ⋯ r^{n}=x, n=1,2,3,\cdots r n = x , n = 1 , 2 , 3 , ⋯
在复平面上，1 1 1 n n n n n n 正多边形的顶点 ，但最多只可有两个顶点同时标在实数线上。
z n = 1 z^{n}=1 z n = 1 z z z n n n n n n 1 1 1 3 3 3
将单位圆等分成 n n n n n n n n n n n n n n n ω n 1 \omega_{n}^{1} ω n 1 n − 1 n-1 n − 1 ω n 2 , ω n 3 , . . . . . . , ω n n \omega_{n}^{2},\omega_{n}^{3},......,\omega_{n}^{n} ω n 2 , ω n 3 , . . . . . . , ω n n w n k = w n k − 1 ⋅ w n 1 ( 2 ≤ k ≤ n ) w_{n}^{k}=w_{n}^{k-1}\cdot w_{n}^{1}\ (2 \leq k \leq n) w n k = w n k − 1 ⋅ w n 1 ( 2 ≤ k ≤ n )
由欧拉公式 e i π + 1 = 0 e^{i\pi}+1=0 e i π + 1 = 0 ω = e i θ = c o s θ + i ⋅ s i n θ \omega=e^{i\theta}=cos\theta+i \cdot sin\theta ω = e i θ = c o s θ + i ⋅ s i n θ
很容易得出下列公式：
ω n n = ω n 0 = 1 \omega_{n}^{n}=\omega_{n}^{0}=1 ω n n = ω n 0 = 1
ω n k = e 2 π k n i \omega_{n}^{k}=e^{\frac{2 \pi k}{n}i} ω n k = e n 2 π k i
ω n k = c o s ( 2 π k n ) + i ⋅ s i n ( 2 π k n ) \omega_{n}^{k}=cos(\frac{2 \pi k}{n})+i \cdot sin(\frac{2 \pi k}{n}) ω n k = c o s ( n 2 π k ) + i ⋅ s i n ( n 2 π k )
单位根性质 折半引理 ω 2 n 2 k = ω n k \omega_{2n}^{2k}=\omega_{n}^{k}
ω 2 n 2 k = ω n k
Proof :
从几何意义来看，两者表示的向量终点是一样的。
ω 2 n 2 k = c o s ( 2 π 2 k 2 n ) + i ⋅ s i n ( 2 π 2 k 2 n ) = c o s ( 2 π k n ) + i ⋅ s i n ( 2 π k n ) = ω n k \omega_{2n}^{2k}=cos(2\pi\frac{2k}{2n})+i\cdot sin(2\pi\frac{2k}{2n})=cos(2\pi\frac{k}{n})+i\cdot sin(2\pi\frac{k}{n})=\omega_{n}^{k}
ω 2 n 2 k = c o s ( 2 π 2 n 2 k ) + i ⋅ s i n ( 2 π 2 n 2 k ) = c o s ( 2 π n k ) + i ⋅ s i n ( 2 π n k ) = ω n k
这条引理可以扩展为：ω m n m k = ω n k \omega_{mn}^{mk}=\omega_{n}^{k} ω m n m k = ω n k
消去引理 ω n k + n 2 = − ω n k \omega_{n}^{k+\frac{n}{2}} = -\omega_{n}^{k}
ω n k + 2 n = − ω n k
Proof :
从几何意义来看，这两者表示的向量终点是相反的，左边较右边在单位圆上多转了半圈。
ω n k + n 2 = c o s ( 2 π k + n 2 n ) + i ⋅ s i n ( 2 π k + n 2 n ) = c o s ( 2 π k n + π ) + i ⋅ s i n ( 2 π k n + π ) = − c o s ( 2 π k n ) − i ⋅ s i n ( 2 π k n ) = − ω n k \omega_{n}^{k + \frac{n}{2}} = cos(2 \pi \frac{k + \frac{n}{2}}{n}) + i \cdot sin(2 \pi \frac{k + \frac{n}{2}}{n}) = cos(2 \pi \frac{k}{n} + \pi) + i \cdot sin(2 \pi \frac{k}{n} + \pi) = -cos(2 \pi \frac{k}{n}) - i \cdot sin(2 \pi \frac{k}{n}) = - \omega_{n}^{k}
ω n k + 2 n = c o s ( 2 π n k + 2 n ) + i ⋅ s i n ( 2 π n k + 2 n ) = c o s ( 2 π n k + π ) + i ⋅ s i n ( 2 π n k + π ) = − c o s ( 2 π n k ) − i ⋅ s i n ( 2 π n k ) = − ω n k
参考资料
