理解傅里叶分析与傅里叶变换

脑电图（Electroencephalography，EEG）和皮质脑电图（Electrocorticography，ECoG）能够捕捉脑电波，而这些脑电波表现为一定频率的震荡波，比如 alpha 波在 8-13 Hz 范围内，beta 波在 13-30 Hz 等。这就使得傅里叶分析在对于脑电进行信号分析中特别有用。

傅里叶分析基本思想

傅里叶分析的基本思想很简单，就是要将一个信号分解为不同频率的正弦和余弦波的加权和，而这一加权和展开式就叫做傅里叶级数或者傅里叶展开（准确地说，是傅里叶三角级数）。用公式来表示：

$s(t)=\frac{a_0}{2}+\sum\limits_{i=1}^{\infin}{a_i\cos{(i\omega t)}}+\sum\limits_{i=1}^{\infin}{b_i\sin{(i\omega t)}}$

我之前在理解这一公式的时候遇到一些困难，所以我把理解的过程写在下面。注意！理解并非证明，这些都是不严格的。

我们知道向量内积的概念，例如 $\begin{bmatrix}1\\2\\3\end{bmatrix}\cdot\begin{bmatrix}4\\5\\6\end{bmatrix}=\begin{bmatrix}1\cdot 4\\2\cdot 5\\3\cdot 6\end{bmatrix}$，它可以用来定义向量的正交，内积空间中两向量的内积为 0，则它们正交。

然后进行拓展，把无穷数列设想为一个无穷维向量，显然这个向量的元素构成的集合（注意即使等值也要看做不同元素）和自然数集等势。这或许比较好理解，那么，一元函数其实也可以被看作是无穷维向量——只不过就是维数再多些罢了。

在这个意义上，函数也能定义正交。类似地，设想对于 $\forall x\in\R$，取 $f(x)\cdot g(x)$ 的一切可能取值并相加，如果结果为 0，那么就说 $f$ 和 $g$ 正交。这不就是积分吗？于是 $f$ 和 $g$ 正交就可以被定义为：

$\int_{-\infin}^{\infin}f(x)\cdot g(x)dx=0$

你会发现正弦函数和余弦函数在任意整数倍周期内积分为 0。于是可以得到下式（其中 T 为 周期）：

$\int_{-\frac{T}{2}}^{\frac{T}{2}}\sin{(kx)}\cos{(kx)}dx=0$

其中 $k\in\N$，正交性显然。

回到傅里叶展开的公式。为什么表示波形要写成这个样子？只用 $\sin$ 或者 $\cos$ 行不行？答案是不行。确切地说不是不行，而是不合适，因为本身傅里叶展开就是一种近似。这种不合适性我认为可以通过以下命题来说明：任意一个形如 $\sin{kx}$ 的正弦函数不能表示为任意多个形如 $\cos{kx}$ 的余弦函数的和。这是由正交的性质决定的。或者也可以思考函数奇偶性，也能发现这个命题的正确性。傅里叶展开对于此类函数的目的肯定是将它们完好无损地展开，而仅仅使用余弦函数远远没有正余弦并用来得合适，这就是为什么展开要同时使用正余弦函数。实际上，$\sin{kx}$ 和 $\cos{kx}$ 正是傅里叶展开中用到的一组标准基。

那么第二个问题是，这种展开真的有效吗？凭什么这样就能近似任何波形呢？这正是傅里叶所宣称的，他当时基于面临的问题宣称任何温度分布都能写成正弦波和的形式。今天的人们已经能够证明如下定理：

定理 设 $f$ 是周期为 $2\pi$ 的连续函数，在 $x$ 点处，如果 $f$ 的导数有定义，则 $f$ 的傅里叶级数在 $x$ 点处收敛于 $f(x)$。

具体证明略，可参看《小波与傅里叶分析基础》（Albert Boggess, Francis J. Narcowich, 2004）第 60 页的证明。

第三个问题是，注意到傅里叶展开中用的是一系列基波和谐波。为什么要取一系列基波和谐波，而不是任取一些不同的波？毕竟他本来并没有强调必须要用一系列的基波和谐波。这是因为基波和谐波具有正交性和完备性，上面已经说明了正交性，下面说明一下完备性。我们不妨假设有一个函数已经被展开为任意多个（甚至无限个）正弦函数和余弦函数的和，但没有遵循傅里叶展开的形式。对所有正弦函数和余弦函数的频率取其最大公因数作为基波频率，于是可以获得一系列的基波和谐波。依照最大公因数的定义，显然原展开中的任意一个正弦函数或者余弦函数都能在这一系列基波和谐波中找到，于是总有这样一系列的基波和谐波可以囊括任取的不同的波。因此，如果能够不按照傅里叶展开的形式将一个函数已经被展开为任意多个（甚至无限个）正弦函数和余弦函数的和，那么这也能够扩展为傅里叶级数的形式，而傅里叶级数的有效性上面已经证明，因此，按照傅里叶级数这一公式是具有相当合理性的。

离散傅里叶变换与快速傅里叶变换

傅里叶级数可以写成更加简练的形式，或许你已经在一些地方看到过：

$s(t)=\sum\limits_{n=-\infin}^{\infin}c_ne^{int}$

如何从之前的形式转换为这一形式，在这里就不进行细致的证明，只需知道他们虽然形式有别但实质无异即可。这里的 $c_n$ 被称为傅里叶系数，函数到其傅里叶系数的对应，定义了一个从时域到频域的映射，这一映射就是傅里叶变换（Fourier transform，FT）。

注意，计算机只能计算离散的数据，并且 BCI 中通常在离散的时间间隔内对大脑信号进行采样，所以就必须引入离散傅里叶变换（discrete Fourier transform，DFT）。

取函数在一个周期中等分格点上的值来表示这个函数，于是有向量 $\boldsymbol{s}$，而那一列简谐波 $e^{int}$ 实际上就可以写成如下形式：

$\begin{bmatrix}1\\1\\\vdots\\1\end{bmatrix},\begin{bmatrix}1\\\omega_n\\\vdots\\\omega_n^{n-1}\end{bmatrix},\cdots,\begin{bmatrix}1\\\omega_n^{n-1}\\\vdots\\\omega_n^{(n-1)^2}\end{bmatrix}$

其中 $\omega_n=e^{\frac{2\pi}{n}i}$。不妨研究一下这一系列的向量：第二个向量的第三个分量为 $\omega_n^2=e^{\frac{2}{n}2\pi i}$，表示 n 等分中第二个格点上简谐波的取值；第三个向量的第二个分量似乎和这个向量一样，但实际上应该看作 $\omega_n^2=e^{\frac{2\cdot 2\pi}{n}i}$，表示简谐波周期的变化。总而言之，这一列简谐波是 $\mathbb{C}^n$ 的一组正交基，而 DFT 得到的就是 $\boldsymbol{s}$ 在这组正交基下的坐标。把这列简谐波并置为矩阵 $F_n$，即傅里叶矩阵，计算 $\boldsymbol{x}=F_n^{-1}\boldsymbol{s}$，即为离散傅里叶变换。

快速傅里叶变换（fast Fourier transform，FFT）是对于上述计算过程的改进，简单来说就是采用分治法的思想，将傅里叶矩阵拆分为多个子矩阵来计算，从而将时间复杂度从 $O(T^2)$ 改进为 $O(T\cdot logT)$。有如下定理：

定理 若有 $D_n=\text{diag}(1,\omega_{2n},\cdots,\omega_{2n}^{n-1})$ 是一个对角矩阵，$P_{2n}=\begin{bmatrix}e_1,e_3,\cdots,e_{2n-1},e_2,e_4,\cdots,e_{2n}\end{bmatrix}$ 是把单位矩阵的奇数列和偶数列分组按照顺序排列得到的置换矩阵，于是有

$F_{2n}P_{2n}=\begin{bmatrix}I_n & D_n\\ I_n& -D_n\end{bmatrix}\begin{bmatrix}F_2&\\& F_2\end{bmatrix}$

这种递归式的求解方法就是快速傅里叶变换。