6.4 稀疏傅里叶变换的定义在线视频

同学们好

接下来两节课

我们将学习一种在信号处理领域

相对比较前沿的算法

稀疏分数傅里叶变换

在此之前

作为理论基础和铺垫

让我们先了解

稀疏傅里叶变换的基本定义

主要的内容分为三个部分

第一部分讲

稀疏傅里叶变换的思想起源

也就是说学者们受到怎样的启发

从而开始探索稀疏傅里叶变换

进而定义了稀疏傅里叶变换

第二部分内容是

稀疏傅里叶变换的定义推导

由于算法流程比较复杂

本节课我们仅选取算法核心部分做介绍

为下节课

稀疏分数傅里叶变换的介绍做铺垫

第三部分

对这节课的内容做一个总结

那么稀疏傅里叶变换是怎么来的呢

我们都知道

很多自然界采集或工程中处理的信号

在时域或频域都只有个别点上

有比较大的幅值

而在其他点基本上是噪底

我们一般称

信号的这种结构特性为稀疏性

而具有稀疏性结构的信号

称之为稀疏信号

对于这一类信号

我们一般对它的噪底如何波动并不关心

而我们真正关心的

是它携带我们感兴趣信息的

那些幅值较高的频谱点坐标位置和幅度

那么 有没有办法

利用这类信号所呈现出的稀疏结构特征

通过放弃估计那些

我们并不关心的噪底波动

来降低计算资源开销呢

答案是肯定的

通过巧妙的算法设计

我们可以实现这一目标

那么具体怎么做呢

麻省理工学院的研究人员提出

可以使用若干次比较少的点数的

快速傅里叶变换

来定位和估计

这些稀疏大值点的位置和幅度

具体来说

假设我们是做傅立叶正变换

也就是说从时域变换到频率

那我们就把时域的这些采样点

分别放到几个篮子里

然后每个篮子里的采样点幅值

全部都相加起来

我们再对这几个幅值叠加后的篮子

而不是篮子里一个一个采样点

做傅立叶变换

那么傅里叶变换的点数

就变为了篮子的个数

通过多次使用不同的排列组合方案

将采样点放置到不同的篮子里

并设计一个确定性哈希算法

就可以通过特定的映射关系

使用若干次比较少点数的

快速傅里叶变换来定位

和估计这些稀疏大值点的位置和幅度

那么如何设计这种

从子采样映射到到原频谱的哈希算法呢

或者是已知小点数的傅里叶变换的结果

如何定位在大点数傅里叶变换结果中的

大值的位置呢

为解答这个疑问

我们先做一些简单但是必要的数学准备

这里先介绍三个数学定义

第一个是

取模运算 或称取余运算

取模运算是一类比较基本的数学运算

同学们应该在使用Matlab编程的时候

使用过mod运算

它有两个输入参数a和b

输出是用a除以b未除尽时得到的余数

如果a可以整除b

则取模运算结果是0

第二个定义

大家应该没有接触过

这个模逆运算是为了设计

稀疏傅里叶变换算法所定义的

一个特殊量

对任意一个

1到大N 之间的σ

如果以大N 为模

一般存在一个σ逆

其满足的条件是

σ与σ逆模N的时候

余数是1

有了以上两个数学定义

那就很方便定义

稀疏傅里叶变换中的时域重排操作

重排后的时域信号小s 的坐标

就对应于原本的时域信号小x的坐标

乘以一个σ再对大N 取模

那么就可以证明

信号关于重排因子

σ的时域重排操作

会导致信号频谱

关于 σ逆产生重排

这个重排公式的推导

仅涉及简单的信号与系统课程的知识

留作感兴趣的同学课下尝试证明

以此为基础

我们看一个简单的

稀疏傅里叶变换算法示例

假设我们有一个原始数据长度为

大N等于16点的信号

其频谱中有唯一一个大值频谱点

为方便讨论

假设将其放置到大B等于8个篮子里

为了能够从8点的傅里叶变换哈希回

原始的16点傅里叶变换

我们将原始信号

关于重排因子σ做信号重排

重排后的信号

在时序坐标位置上被完全打乱

再对乱序后的时域信号做预滤波

滤波器窗长为w=12点

将滤波后的数据点

分别放到8个篮子里

每个篮子里两个点直接相加

再对输出的8个篮子点做FFT

得到频谱尖帽子z

现在的问题关键在于

如何使用刚刚介绍的信号重排公式

将得到的8点频谱尖帽子z映射回

乱序后的16点信号的频谱尖帽子y

乃至原始

16点信号的频谱尖帽子x

对于重排因子σ=3

其对应的16为模的模逆是

σ逆=11

大家可以验算一下

假设大值点尖帽子z的第1个点

那么对应重排后但未分篮子的频谱

尖帽子y中的第1 2两个频谱点

通过信号重排公式

我们可以推知

这两个频谱点

进一步分别对应于尖帽子x

也就是原频谱中的11 6两个频谱点

接下来我们再看一下

重排因子σ=5的情况

对应模逆是σ逆=13的情况

此时大值点会出现在

尖帽子z的第7个频谱点

对应重排后但未分篮子的频谱

尖帽子y中的第13 14两个频谱点

通过信号重排公式

我们可以推知

这两个频谱点

进一步分别对应于尖帽子x

也就是原频谱中的9 6两个频谱点

同理

我们也可以考察重排因子σ=7

σ逆=7的情况

我们发现尖帽子x

也就是原频谱中的15 6两个频谱点

存在大值

通过三次频谱估计

对于使用8个数据篮子

估计16个傅里叶变换的情况

1个小点数傅里叶变换得到的频谱大值点

会映射回原始长信号频谱中的2个点

因为16/8=2

但是这两个点中只有一个点

对于不同的重排因子σ

总是保持坐标位置不变

而另一个点的坐标

是与σ选取有关的

稀疏傅里叶变换

就判别位置不变的频谱点

是原始信号中真实存在的大值频谱点

而另外一个点

是子采样傅里叶变换带来的伪峰

大值频谱点

幅值取几次重排频谱中真实谱峰

幅值的中值

取中值比取平均值更鲁棒

因为取平均可能受

偏离真值较大的离群值影响

到这里

稀疏傅里叶变换

完成了只使用两三次8点FFT

估计16点数据频谱的任务

有同学们可能会问

我做两三次8点FFT

得到了一次16点FFT的结果

计算复杂度好像并没有减少啊

（好像反倒增加了计算量？）

这是因为我们举的例子中

原始信号数据点数太短

且分到每个篮子里的数据点才为2点

对于超长点数的数据

如果分到每个篮子里的

数据点数能更多一点

我们就能用几次相对于

原信号长度小得多的

点数的快速傅里叶变换

来替代一次超长点数的快速傅里叶变换了

因此 对于我们刚刚介绍的

最初始版本的稀疏傅里叶变换

只有在待处理数据点数

超过特定的数量级

其计算复杂度

才会优于传统快速傅里叶变换

近年来

随着稀疏傅里叶变换理论的发展

算法版本的迭代

其计算复杂度优势又有了质的提升

感兴趣的同学

可以在课后继续追踪相关文献

去详细了解

我们对这节课的内容来做一个总结

稀疏傅里叶变换的思想就是

使用几次小点数的FFT

代替大点数的傅里叶变换的计算

算法的关键

在于利用信号重排加入随机性

确保可以成功映射回原谱

大家可以回忆下

如何做到这一点的

算法从根本上

其实是巧妙利用了信号稀疏性

这种结构先验信息

获得了降低计算复杂度的收益

这就是本节课我们所学习的

稀疏傅里叶变换的定义推导

谢谢大家