DFT and FFT

Linear_Algebra Algorithm Maths

What is DFT

DFT for Discrete Fourier Transform,顾名思义，DFT是一种转换方式，那是什么的转换方式呢？从线性代数的角度，简单的来说就是利用单位根去从多项式的一种表达形式转换为另外一种表达形式。DFT可以说是FFT的前一步。

Principle Root of Unity

1的n次单位根(root of unity)：$\omega_n =\sqrt[n]{1}=e^{2\pi i/n}$
这里不多做说明，相关知识在GSLA第九章。直观上可以想象复平面上的单位圆被均分为n份。

Representation of Polynomial：

（1）coefficient represent:
对于一个n阶多项式：$A(x)=a_0+a_1x+a_2x^2+…+a_{n-1}x^{n-1}$
我们可以用一个coefficient vector来表示:$(a_0,a_1,…,a_{n-1})$

(2)point-value represent:
设$y_k=A(x_k)$，那么我们可以用n个点来确定一个n-1多项式：
$\{(x_0,y_0),(x_1,y_1),…,(x_{n-1},y_{n-1})\}$
这种用一组点来求对应的多项式的过程叫多项式插值（interpolation)。用这种表示方法去确定一个唯一的n-1阶多项式的条件是有n个x分量不同的点。

现证明：n个不同的点可以唯一确定一个n-1阶多项式
分析：多项式的系数可以唯一确定一个多项式，所以我们把问题转换成：n个不同的点可以唯一确定一个coefficient vector

首先我们有n个方程：
$y_0=a_0+a_1x_0+a_2x_0^2+…+a_{n-1}x_0^{n-1}$
$y_1=a_0+a_1x_1+a_2x_1^2+…a_{n-1}x_1^{n-1}$
.
.
$y_{n-1}=a_0+a_1x_{n-1}+a_2x_{n-1}^2+…+a_{n-1}x_{n-1}^{n-1}$
写成矩阵形式就是：
$\begin{bmatrix}1&x_0\cdots&x_0^{n-1}\\1&x_1\cdots&x_1^{n-1}\\\vdots&\ddots&\vdots\\1&x_{n-1}\cdots&x_{n-1}^{n-1}\end{bmatrix}$ $\begin{pmatrix}a_0\\a_1\\\vdots\\a_{n-1}\end{pmatrix}$

=$\begin{pmatrix}y_0\\y_1\\\vdots\\y_{n-1}\end{pmatrix}$

留意到这个矩阵是之前GSLA第五章提到过的Vandermonde matrix，它的行列式为：$\prod\limits_{0 \le j<i \le n-1}x_i-x_j$
因为$x_i \not =x_j$，所以它的determinant不为0，即这是一个可逆矩阵，$Aa=y$,有唯一解为$a=A^{-1}y$
所以n个不同点可以唯一确认一个n-1阶多项式
Q.E.D.

The DFT

刚才我们证明了，用n个x分量不同的点可以唯一确定一个n-1阶多项式，所以我们可以通过巧妙的选择这n个点来达到一些目的。DFT选择了用$\omega_n^k$来作为n个点的x分量。

将$\omega_n^k$代入刚才的矩阵中，我们就得到了一个n阶Fourier matrix：
$\begin{bmatrix}1&1\cdots&1\\1&\omega_n\cdots&\omega_n^{n-1}\\\vdots&\ddots&\vdots\\1&\omega_n^{n-1}\cdots&\omega_n^{(n-1)^2}\end{bmatrix}$

记作$F_n$,$F_n{ij}=\omega_n^{(i-1)(j-1)}$
记$y=(y_0,y_1,…,y_{n-1}）$，其中$y_k=A(\omega_n^k)=\sum\limits_{j=0}^{n-1} a_j\omega_n^{kj}$
记作$y=DFT_n(a)$,$a=DFT_n^{-1}(y)$

这就是DFT的过程，$\Theta(n^2)$的复杂度，但是通过$\omega_n^k$的一些性质还有分治法，我们可以将复杂度下降为$\Theta(nlgn)$，其实就是FFT(Fast Fourier transform)

From DFT to FFT

-TBC-

*Prove of Vandermonde Determinant

-TBC-