2012年，Technology Review评选出十大科技进展，其中一项是由MIT计算机科学和人工智能实验室研究出的稀疏傅里叶变换（Sparse Fast Fourier Transform）。据介绍，这项新技术比传统的FFT快10到100倍，将给数据传输领域带来革命性的进步！

如何理解这个新型傅里叶变换？让我们先从音乐的视角重新理解一下最基本的傅里叶变换！

https://v.qq.com/txp/iframe/player.html?vid=l1318lspmfi&width=500&height=375&auto=0

钢琴的每个琴键都对应一个特定频率的声音。例如，一个比较有名的频率是国际标准音A（440赫兹）。

不过，每次只演奏一个音符太单调了，我们来尝试几个音符同时演奏。有趣的是，两个各不相关的声音结合起来，就创造一个全新的独特声音。

快速傅立叶变换（FFT）可以让我们将这个新的声音解构为原始的频率，从本质上得到这个和弦是由哪些琴键组成的。如下图所示，是一个单音的波形和频谱。

然而生活中的声音要比音乐厅里纯净的和弦复杂得多。现在我们再给钢琴加一个歌手伴奏。人的声音频率范围很宽，多种多样的频率组成了多种多样的声音（词语）。正如下面的图片，音频信号可能会非常非常复杂。

显然，说出不同词语时的音频信号，就不像上面的标准音A那样光滑波动了！

现在，我们已经有点明白FFT了，现在来看看MIT的稀疏FFT。原本的FFT将计算出每个频率的幅度，但我们也许可以利用这样一个事实，即大部分的频率将集中在C、A和F周围！

因此，如果我们只计算组成最终音频信号的三个频率，可以复制出一个足够接近于原音乐乐谱的声音。这就是稀疏傅里叶变换(SFFT)在做什么。

我们都知道FFT（快速傅里叶变换）要比DFT（离散傅里叶变换）快得多：

那么SFFT（稀疏傅里叶变换）呢？他的算法复杂度和序列的稀疏度K有关。稀疏度K表示信号序列中非零元素的个数。比如有这样一个序列：{0,1,0,0,1}，它只有2个非零元素，它的稀疏度K=2.

当序列元素个数N一定时，运算时间与稀疏度K的关系（红线表示SFFT,黑线表示FFT）：

当稀疏度K一定时，运算时间与序列元素个数n（红线表示SFFT,黑线表示FFT）：

由上面的对比可以看到，对于一定长度的信号序列，里面含有的零元素越多，用SFFT处理该信号相比于用FFT处理就会越高效。而对于一个稀疏度保持定值的信号序列，里面含有的元素数量越多，用SFFT处理该信号相比于用FFT处理就会越高效。

事实上这很好理解，因为FFT无法识别信号序列中的零元素，它的算法对于零元素以及非零元素一视同仁；而SFFT则能够识别出这些零元素，只对非零元素进行运算，省去了没有必要的运算，运算效率相比FFT自然大为提升。

那么SFFT又是如何识别出序列中的零元素，如何只提取出序列中的非零元素进行运算的呢？SFFT对于我们的生活又会有哪些帮助呢？敬请期待下期电子伊甸园，每周五晚我们不见不散。

作者

▼

白玉晶 徐佩奇 赵永成

本文转载自

▼

电子伊甸园