什么是稀疏傅里叶变换？

#1 楼

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

此处介绍的稀疏傅里叶变换算法是一种技术。用于计算那些$ k $输出的复杂度低于基于FFT的方法。本质上，因为$ N-k $输出为零，所以您可以通过在算法内部使用快捷方式甚至不生成那些结果值来节省一些精力。尽管FFT的复杂度为$ O（n \ log n）$，但稀疏算法在稀疏频谱情况下的复杂度为$ O（k \ log n）$。

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

根据其结果的一张图（如下图所示），相对于FFTW（麻省理工学院的其他一些人制造的优化的FFT库）而言，提高性能的分界点大约只有$输出变换系数的第\ frac {1} {2 ^ {11}} $ th至$ \ frac {1} {2 ^ {10}} $ th不为零。同样，在此演示中，他们指出当$ \ frac {N} {k} \ in [2000，10 ^ 6] $中时，稀疏算法提供了更好的性能。



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

我需要通读一些文献以获得更好的理解感觉到这种技术在实际问题上的实用性，但是对于某些类别的应用程序，可能是合适的。

#2 楼

我尚未阅读有关sFFT的文章，但我的感觉是，将FFT固定在后面的想法是在利用k稀疏的先验。因此，不必计算FFT系数的所有项，而是仅计算其中的k个。因此，对于k稀疏信号，复杂度为O（klog n），而不是传统FFT的O（nlog n）。压缩感知背后的想法是，您可以从不同域中抽取的稀疏随机样本中恢复稀疏数据（例如，从随机稀疏频率数据（即MRI）中恢复稀疏图像。”问题是什么是“稀疏随机样本”？我认为这可能是通过将稀疏数据随机投影到较低的（测量）子空间而收集的样本。

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

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

结论是，cs是采样理论的一大进步，只要这些信号足够稀疏，就可以提供一种有效的信号采样方法。因此，cs是一个抽样理论，任何打算将其用作分类或识别技术的人都会误导该原理。有时，我会找到一些标题为“基于压缩感知的.....”的论文，我认为此类论文的原理是利用l1最小化而不是cs，最好使用“基于l1最小化...”。 ”。

如果我错了，请纠正我。

#3 楼

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

稀疏恢复/压缩感测的PS技术并与其相连L1最小化在现代信号处理中，尤其是在与傅立叶变换的结合中，使用了很多，实际上，现代信号处理是必须要知道的但是，在使用傅立叶变换作为解决稀疏恢复问题的方法之一之前，在这里我们看到了相反的问题-傅立叶变换的稀疏恢复。 -blanche.blogspot.com/

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

如果我弄错了方法，请随时纠正我。