该算法的思想是这样的：假设您有一个长度为的信号，该信号在频域中是稀疏的。这意味着如果你要计算它的离散傅里叶变换，将会有少量非零其他可以忽略不计。获得所需的个输出的一种方法是对整个序列使用FFT个非零值。$N$$k \ll N$$N-k$$k$$k$

这里介绍的稀疏傅里叶变换算法是一种计算那些输出的技术，其复杂度低于基于 FFT 的方法。本质上，由于输出为零，因此您可以通过在算法内部采取捷径甚至不生成这些结果值来节省一些精力。虽然 FFT 的复杂度为 ，但对于稀疏谱情况，稀疏算法的复杂度可能更低，为$k$$N-k$$O(n \log n)$$O(k \log n)$

对于更一般的情况，频谱“有点稀疏”但有超过个非零值（例如，对于嵌入噪声中的许多音调），它们提出了估计个最大输出的算法的变体，其中的时间复杂度，它也可能没有 FFT 复杂。$k$$k$$O(k \log n \log \frac{n}{k})$

根据他们的结果图（在下图中再现），对于 FFTW（一个优化的 FFT 库，由 MIT 的其他一些人制作）提高性能的交叉点大约是只有 -th 到 -th 的输出变换系数是非零的。此外，在本演示文稿中，他们指出稀疏算法在时提供更好的性能。$\frac{1}{2^{11}}$$\frac{1}{2^{10}}$$\frac{N}{k} \in [2000, 10^6]$

这些条件确实将算法的适用性限制在您知道信号频谱中可能很少有非常大的峰值的情况下。他们在其网站上引用的一个示例是，平均而言，通常用于图像和视频压缩的 8×8 像素块在频域中几乎 90% 是稀疏的，因此可以从利用该属性的算法中受益。这种稀疏程度似乎与该特定算法的应用程序空间不相符，因此它可能只是一个说明性示例。

我需要更多地阅读文献以更好地了解这种技术在实际问题上的实用性，但对于某些类别的应用程序，它可能是合适的。

我还没有读过关于 sFFT 的论文，但我的感觉是，将 FFT 固定在后面的想法是利用了 k-sparsity 的先验。因此，不必计算 FFT 系数的所有条目，而只需计算其中的 k 个。这就是为什么对于 k 稀疏信号，复杂度是 O(klog n) 而不是传统 FFT 的 O(nlog n)。

无论如何，关于@rcmpton 的评论，通过说“压缩感知背后的想法是，您可以从来自不同域的稀疏随机样本中恢复稀疏数据（例如，从随机稀疏频率数据（即 MRI）中恢复稀疏图像） 。” 问题是什么是“稀疏随机样本”？我认为它可能是通过将稀疏数据随机投影到某个较低（测量）子空间来收集的样本。

据我了解，压缩感知的理论框架主要包括三个问题，稀疏性、测量和恢复。通过稀疏性，它涉及为某些类别的信号寻求稀疏表示，这是字典学习的任务。通过测量，它涉及寻求一种有效的方式（计算效率和可恢复）来测量数据（或将数据投影到较低的测量空间），这是测量矩阵设计的任务，例如随机高斯矩阵，结构化随机矩阵，. ...通过recovery，是稀疏正则化线性反演问题，l0，l1，l1-l2，lp，l-group，blabla...，结果算法多种多样，匹配追踪，软阈值，硬阈值，基础追踪，贝叶斯，....

诚然，“cs是L1范数的最小化”，L1范数是cs的一个基本原理，但cs不仅仅是L1范数的最小化。除了上述 3 部分之外，还有一些扩展，如结构化（组或模型）压缩感知，其中也利用了结构化稀疏性，并被证明可以大大提高恢复能力。

总而言之，cs 是采样理论的一大步，提供了一种对信号进行采样的有效方法，前提是这些信号足够稀疏。因此，cs 是一种抽样理论，任何将其用作分类或识别技术的人都会误导这一原则。偶尔，我发现一些题为“基于压缩感知......”的论文，我认为这种论文的原理是利用l1-minimization而不是cs，最好使用“l1-minimization based .... ”。

如果我错了，请纠正我。

我浏览了这篇论文，我想我对这个方法有了大致的了解。该方法的“秘诀”是如何在频域中获得输入信号的稀疏表示。以前的算法使用一种蛮力来定位主要稀疏系数。这种方法使用称为“空间恢复”或“压缩感知” 维基文章的替代技术在这里。这里 使用的稀疏恢复的确切方法看起来类似于“硬阈值” - 一种主要的稀疏恢复方法。

稀疏恢复/压缩感知的 PS 技术以及与之相关的 L1 最小化在现代信号处理中，尤其是与傅里叶变换相关的应用中得到了广泛应用。事实上，现代信号处理必须了解这一点。但之前傅里叶变换被用作解决稀疏恢复问题的方法之一。在这里，我们看到相反的情况——傅里叶变换的稀疏恢复。

概述压缩传感的好网站： nuit-blanche.blogspot.com/

PPS 对先前评论的回答 - 如果输入信号不完全稀疏，则它是有损的。

如果我的方法有误，请随时纠正我。