轻松点的离散傅立叶变换

概述

一般来说，标准的介绍傅立叶变换会从“连续“的”周期“的信号的傅里叶级数开始，完了再推广到连续无周期信号的傅里叶变换，或是还要介绍离散时间傅立叶变换（DTFT）。但实际中，我们只能处理”有限长度“的离散傅立叶变换，公式如下：

$\begin{aligned}DFT:\quad &X[k] = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi kn/N}, \quad k=0,1,2,...,N-1 \\IDFT:\quad &x[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k] e^{j 2\pi kn/N}, \quad n=0,1,2,...,N-1 \end{aligned}$

这里遵循工程领域的记法，使用 $j$ 作为虚数单位；另外使用 $n$ 作为时域下标， $k$ 作为频域下标； $x[n]$ 表示时域样本，而 $X[k]$ 为频域样本。

我们注意到，这两个公式是两组有限个数据”先逐个相乘，再相加”的运算；而这不正是”内积运算“吗？所以，下面我们将从线性代数的角度来理解DFT运算，我们将抛开函数的Hilbert空间、完备正交函数系、无穷维度空间序列的收敛性等等诸如此类的概念；也无需特别地讨论空间的完备性，因为在域 $\mathbb C$ 或是域 $\mathbb R$ 上的有限维向量空间中，完备性是由域的完备性就可以保证的；这是比较让人愉快的。

由此，我们先将N维信号放到N维实向量空间，但由于实际中我们多以复数域傅立叶变换为主，所以我们下面只考虑 $\mathbb C$ 上的向量空间，基本上就是大家所学的线性代数知识，我们将通过下面讨论获得上面两个公式。

内积

首先，我们引入向量空间的内积运算：

$<\cdot,\cdot> \ :\ {\mathbb C}^N\times {\mathbb C}^N \to {\mathbb C}$ ，定义为： $<\boldsymbol x, \boldsymbol y> = \sum_{n=0}^{N-1}x[n]\ \overline{y[n]}$

这正是我们所熟知的内积运算，并且满足以下性质：

1）关于第一变元的线性性： $<\alpha\boldsymbol x + \boldsymbol y\ , \boldsymbol z>=\alpha+\quad,\forall \boldsymbol x,\boldsymbol y,\boldsymbol z\in {\mathbb C}^N,\forall \alpha \in \mathbb C$

2）共轭对称性： $<\boldsymbol x\ ,\boldsymbol y > = \overline{}\quad,\forall \boldsymbol x,\boldsymbol y\in {\mathbb C}^N$

3）正定性： $<\boldsymbol x\ ,\boldsymbol x> \ \geq\ 0,\forall \boldsymbol x \in {\mathbb C}^N; {\rm and}\ =0 \iff \boldsymbol x = \boldsymbol 0$

很容易验证上面内积的定义满足这些性质，大家曾经肯定都做过相关的练习。另外，到这里就知道为什么上面的内积的定义中，关于第二变元要加上一个丑陋的共轭符号，因为我们需要它满足正定性条件，使得它可以诱导出合法的范数，进而度量距离。

范数

可以由上面的内积诱导出如下欧几里得范数：

$||\boldsymbol x|| = \sqrt{<\boldsymbol x\ , \boldsymbol x>}$ ，易知满足如下性质：

1）正齐次性： $|| \alpha \boldsymbol x|| = |\alpha|\ ||\boldsymbol x||$

2）正定性： $\begin{aligned}&||\boldsymbol x|| \geq 0 , \forall \boldsymbol x \in {\mathbb C}^N\\ &||\boldsymbol x|| =0 \iff \boldsymbol x = \boldsymbol 0\end{aligned}$

3）三角不等式： $||\boldsymbol x + \boldsymbol y|| \leq ||\boldsymbol x|| + ||\boldsymbol y||$

为了水一下文章的长度，我们来证明一下三角不等式，不过按常规我们需要先证明一下Cauchy-Schwarz不等式： $|<\boldsymbol x \ , \boldsymbol y>| \leq ||\boldsymbol x|| \ ||\boldsymbol y||$ ，这里我们无需使用内积的具体形式，而只需要上面的三个公理即可。

Proof: 由内积的正定性可知， $<z\boldsymbol x \ + \boldsymbol y\ ,z\boldsymbol x \ + \boldsymbol y>\ \geq \ 0 , \forall \boldsymbol x \in {\mathbb C}^N,\forall z \in \mathbb C$ 都成立。

我们利用内积关于两个变元的可加性将其展开得：

$<z\boldsymbol x \ ,z\boldsymbol x \ > + ++\ \geq \ 0$

再利用内积关于第一变元的齐次性，和关于第二变元的共轭齐次性得：

$z\overline{z}<\boldsymbol x \ ,\boldsymbol x \ > - z-\overline {z}+\ \geq \ 0$

由于 $z$ 是任意的复数，我们将 $\frac{<\boldsymbol y\ ,\boldsymbol x>}{}$ （这里还需假设 $\boldsymbol x \neq \boldsymbol 0$ ）代入上式得：

$\frac{<\boldsymbol y\ ,\boldsymbol x>\overline{}}{^2} - \frac{}{}-\overline {\frac{}{}}+\ \geq \ 0$

代入 $||\boldsymbol x|| = \sqrt{<\boldsymbol x\ , \boldsymbol x>}$ ，且由内积的共轭对称性，以及一个复数乘以它的共轭等于模的平方，经过化简得：

$\frac{|<\boldsymbol y \ , \boldsymbol x>| ^2}{||\boldsymbol x||^2} - \frac{|| ^2}{||\boldsymbol x||^2} - \frac{|| ^2}{||\boldsymbol x||^2} + ||\boldsymbol y||^2 \geq 0$

即： $|<\boldsymbol y \ , \boldsymbol x>| \leq ||\boldsymbol x|| \ ||\boldsymbol y|| \quad\quad\Box$

Proof of triangular inequality:

$\begin{aligned}||\boldsymbol x + \boldsymbol y ||^2 &\equiv \\&= + + + \\&=||\boldsymbol x||^2 + +\overline{} + ||\boldsymbol y||^2\\&=||\boldsymbol x||^2 + 2Re\{\} + ||\boldsymbol y||^2 \\&\leq ||\boldsymbol x||^2 + 2|| + ||\boldsymbol y|| \\&\leq ||\boldsymbol x||^2 + 2||\boldsymbol x|| \ ||\boldsymbol y|| + ||\boldsymbol y|| \quad ({\rm by\ Cauchy-Schwarz}) \\&=(||\boldsymbol x|| + ||\boldsymbol y||)^2 \\\iff&||\boldsymbol x+\boldsymbol y|| \leq ||\boldsymbol x||+||\boldsymbol y|| \quad \quad \Box\end{aligned}$

正交基的构造

在任一个向量空间中，显然存在无穷的基；而在我们定义了有限维完备内积空间后，我们感兴趣的是那些正交基；显然，在N维向量空间中，存在由N个one-hot向量构成的标准正交基；而我们的有限的离散信号就是用这个基来表示的，设这个基为： $\boldsymbol o_0,\boldsymbol o_1,...,\boldsymbol o_{N-1}$ ，信号为 $\boldsymbol x \in {\mathbb C}^N$ ，则 $\boldsymbol x = \sum_{n=0}^{N-1} x[n] \ \boldsymbol o_n$ 。

但是这样的基的表示对我们来说没有用处，因为它不能捕捉到我们感兴趣的特征，我们感兴趣的是信号中的频率成份分布；所以我们下面将构造出一个基，这个基中的所有向量将会捕捉到信号内的不同的频率成份的强度。

但是，如何构造呢？回想一下，在学习傅立叶变换时，不管是周期信号的傅立叶级数还是非周期信号的傅立叶变换，都使用最基本的复指数正弦波来作为基本的构造函数，当频率不相同时它们就是互相正交的，但是它们或是在有限的连续区间内进行积分，或是在无限的区间进行积分得到积分为0，进而是正交的。

那么我们在有限维向量空间中，我们同样也想在周期函数上进行采样来获得能刻画频率的且是正交的基；而基本的复周期函数就是 $e^{jx}$ ，它的图像是复平面上的一个圆；并且我们进行均匀采样，因而希望N个样本点在圆上是均匀分布的。

这让我们想到1的N次根，设任意的单位长度的复数为 $e^{j\theta}$ ，由 $(e^{j\theta})^N = 1=e^{j2n\pi}$ 解得： $\theta = 2n\pi / N\quad ; n=0, 1, ..., N-1$ ，即 $\mathcal G=\{e^{2\pi n/ N} \quad ; n=0, 1, ..., N-1\}$ 为N个不重复的单位根。重要的是这N个单位根构成了一个Abelian群，群运算定义为复数的乘法运算 $\otimes: \mathcal G\times \mathcal G \to \mathcal G$ ，事实上这是一个循环Abelian群：所有的根都能由群的生成元 $e^{2\pi / N}$ 的若干次幂(自乘若干次)得到。群的多个性质（如交换性）继承自复数乘法运算，下面简单验证一下群 $(\mathcal G, \otimes)$ 关于 $\otimes$ 运算的封闭性：

Proof：任意取两个 $\mathcal G$ 中的元素相乘： $e^{2\pi n/N}\otimes e^{2\pi m/N}=e^{2\pi n/N} e^{2\pi m/N}=e^{2\pi (n+m)/N}$ ，若 $m+n <N$ ，则显然结果还是属于 $\mathcal G$ ；若 $m+n\geq N$ ，则由周期性得： $e^{2\pi(m+n)/N} = e^{2\pi l/ N} ,\quad m+n = pN + l , {\rm and}\ l < N$ ，再次有 $e^{2\pi l/N} \in \mathcal G$ 。另外，当多个元素连乘时，也类似可证。 $\quad \Box$

群的封闭性可以让我们对其中的元素进行任意的相乘而不能跳出去。下面我们再来观察一个性质：设 $z$ 为任意不等于0,1的复数，则有： $\sum_{n=0}^{N-1} z^n = \frac{1- z^N}{1-z}$ ，所以 $\mathcal G$ 内的所有元素相加等于0！（这将意味着下面我们的全1向量正交与所有其它的向量。）

1）我们将 $\mathcal G$ 中的元素按顺序排进一个N维复向量中得到一个非零向量：

令： $\boldsymbol e_1 = [1, e^{2\pi /N}, e^{2\pi 2/N},...,e^{2\pi (N-1)/N}]$ ，它构成我们正交基的第一个成员；遍历该向量的所有元素，刚好绕着复平面单位圆沿着单位根群转了一周，没跳过任一个根；因此对应着提取信号的最低频率成份，具体的物理频率可以根据采样率和FFT点数计算。

2）接下来，我们使用乘向量 $\boldsymbol e_1$ 来生成其它的基向量：

令： $\begin{aligned}\boldsymbol e_1 &=\boldsymbol 1 \odot \boldsymbol e_1 = [1, e^{2\pi 1/N}, e^{2\pi 2/N},...,e^{2\pi (N-1)/N}]\\\boldsymbol e_2 &=\boldsymbol e_1 \odot \boldsymbol e_1 = [1, e^{2\pi 1\times 2/N}, e^{2\pi 2\times2/N},...,e^{2\pi (N-1) \times 2/N}] \\\boldsymbol e_3 &=\boldsymbol e_2 \odot \boldsymbol e_1 = [1, e^{2\pi 1\times 3/N}, e^{2\pi 2\times3/N},...,e^{2\pi (N-1) \times 3/N}] \\\vdots\\\boldsymbol e_{N-1} &=\boldsymbol e_{N-2} \odot \boldsymbol e_1 = [1, e^{2\pi 1\times (N-1)/N}, e^{2\pi 2\times(N-1)/N},...,e^{2\pi (N-1) \times (N-1)/N}] \\\boldsymbol e_{0}=\boldsymbol e_{N} &=\boldsymbol e_{N-1} \odot \boldsymbol e_1 = [1, e^{2\pi 1\times (N)/N}, e^{2\pi 2\times(N)/N},...,e^{2\pi (N-1) \times (N)/N}]\end{aligned}$

其中： $\boldsymbol 1$ 为全1向量， $\odot$ 为阿达玛乘积（Hadamard Product）。

$\boldsymbol e_2$ 是第二个基向量；对应着提取信号中频率的成份，因为从头到位遍历一遍 $\boldsymbol e_2$ 相当于从根1开始每隔一个取一次，相当于在单位圆上绕2圈；对应提取信号中的两倍于最低频率的量。

$\boldsymbol e_3$ 是每隔两个取一次，如此下去，直到最后一个向量 $\boldsymbol e_0$ 构造完成；仔细看实际上 $\boldsymbol e_0$ 是全1向量，对应提取信号的直流分量。我们把最后一个直流向量挪到第一排，构成如下基向量矩阵：

$D = \begin{bmatrix} &1, &1, &1, &... &1 \\ &1, &e^{2\pi 1\times 1/N}, &e^{2\pi 2\times1/N},&...,&e^{2\pi (N-1) \times 1/N}\\&1, &e^{2\pi 1\times 2/N}, &e^{2\pi 2\times 2/N},&...,&e^{2\pi (N-1) \times 2/N}\\&\vdots, &\vdots, & \vdots, &\ddots, &\vdots\\&1, &e^{2\pi 1\times (N-1)/N}, &e^{2\pi 2\times (N-1)/N},&...,&e^{2\pi (N-1) \times (N-1)/N}\\ \end{bmatrix}$

3）我们一直称这些向量为基向量，现在我们来简单证明一下，它们的确构成一个基。由于向量的正交性必然也有线性独立性成立，所以我们直接证明它们两两正交即可。

Proof of Orthogonality：

$\begin{aligned} &= \sum_{n=0}^{N-1} e^{j2\pi kn/N} \ \overline{e^{j2\pi ln/N}} \\& = \sum_{n=0}^{N-1} e^{j2\pi (k-l) n/N}\\&= \begin{cases} &\frac{1 - (e^{j2\pi (k-l)/N)^N}}{1 - e^{j2\pi (k-l)/N}}, &k \neq l \\&\sum_{n=0}^{N-1} 1, &k=l \end{cases} \\&= \begin{cases} &0, &k \neq l \\& N, &k=l \end{cases} \end{aligned}$

所以，的确是正交向量组，又该线性无关向量组包含N个向量，因此构成向量空间的一个基。 $\Box$

投影

既然构造了这个正交基，我们就可以将任意向量 $\boldsymbol x \in {\mathbb C}^N$ 投影到这个基上面得到坐标系数向量 $X \in {\mathbb C}^N$ ，我们称之为离散傅立叶变换DFT，即：

$\begin{aligned}DFT:\quad &X[k] = <\boldsymbol x\ , \boldsymbol e_k> = \sum_{n=0}^{N-1} x[n] e^{-j 2\pi kn/N}, \quad k=0,1,2,...,N-1\end{aligned}$

显然，由 $<\overline{\boldsymbol e_k}, \overline{\boldsymbol e_l}> = \sum_{n=0}^{N-1} e^{-j2\pi kn/N} \ e^{--j2\pi ln/N}=\sum_{n=0}^{N-1} e^{j2\pi ln/N}\ e^{-j2\pi kn/N}= = \delta_{lk}\cdot N$

因此，共轭基向量也构成了一个基，而把 $X$ 投影到共轭基上得到：

$\begin{aligned} &= \sum_{k=0}^{N-1} X[k]\ e^{--j2\pi kn/N} \\&=\sum_{k=0}^{N-1} ( \sum_{m=0}^{N-1} x[m]\ e^{-j2\pi km/N}) \ e^{j2\pi kn/N} \\&= \sum_{m=0}^{N-1} x[m]\ ( \sum_{k=0}^{N-1} e^{-j2\pi km/N} \ e^{j2\pi kn/N} )\\&= \sum_{m=0}^{N-1} x[m]\ \sum_{k=0}^{N-1} e^{j2\pi k(n-m)/N} \\&= \sum_{m=0}^{N-1} x[m]\ \delta_{m,n} \cdot N\\&=N\cdot x[n]\end{aligned}$

因此，我们也把 $\frac{1}{N} <X, \overline{\boldsymbol e}_n> = \frac{1}{N} \sum_{k=0}^{N-1} X[k]e^{j2\pi kn/N}, n=0,1,...,N-1$ 称为傅立叶逆变换。

最后编辑于：2022.10.27 16:40:31

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 204,793评论 6赞 478
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 87,567评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 151,342评论 0赞 338
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,825评论 1赞 277
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,814评论 5赞 368
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,680评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,033评论 3赞 399
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,687评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 42,175评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,668评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,775评论 1赞 332
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,419评论 4赞 321
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,020评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,978评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,206评论 1赞 260
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,092评论 2赞 351
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,510评论 2赞 343

轻松点的离散傅立叶变换

概述

内积

范数

正交基的构造

投影

推荐阅读更多精彩内容