ICMLJun, 2018

信号和噪音统计信息不可知的正交匹配追踪

PDF
TL;DR本篇论文提出了一种名为残差比阈值法（Residual Ratio Thresholding，RRT）的新技术，可以在没有关于疏密性和噪声统计的任何先验知识情况下运行正交匹配追踪（Orthogonal Matching Pursuit，OMP），并为其建立有限样本和大样本支持恢复保证。分析结果和实数及虚数数据集的数值模拟表明，RRT 的性能与具有先验知识的 OMP 相当。
orthogonal matching pursuitsparse vectorslinear regression modelsresidual ratio thresholdingsupport recovery guarantees
发现论文，激发创造
  • 正交匹配追踪：布朗运动分析

    本文使用正交匹配追踪算法研究了稀疏信号恢复的问题并发现，使用高斯测量矩阵的低噪声情况下，仅需较少的测量次数和无限趋近于 1 的概率即可实现稀疏向量的恢复，该结果还与 lasso 方法的恢复次数相匹配。

    May, 2011

  • 广义正交匹配追踪

    本研究提出一种名为 generalized OMP 的方法，是针对稀疏信号重建效率进行的 OMP 算法推广，每次迭代找到多个正确的索引进行选择，相比于 OMP 算法，gOMP 算法迭代次数更少，且可以重建任何 K 稀疏信号，且仿真结果表明 gOMP 算法是一种高效的信号恢复方法，具有与 L1 极小化技术类似的恢复性能。

    Nov, 2011

  • 替换正交匹配追踪

    本文提出了一种新的部分硬阈值算子用于压缩感知问题，并通过该算子构建了一组新的迭代算法，其中 Orthogonal Matching Pursuit with Replacement (OMPR) 表现最佳。通过将局部敏感哈希技术与 OMPR 算法相结合，本文提出了第一个被证明具有亚线性（在维度上）性能的稀疏恢复算法。实验结果表明，相比现有方法，本文方法在大规模问题上更为快捷和鲁棒。

    Jun, 2011

  • 在噪声存在的情况下使用正交匹配追踪支持恢复：一项新的分析

    本文研究压缩感知领域的稀疏信号恢复问题，通过对正交匹配追踪算法在噪声情况下的研究，分析了两种信噪比设置情况下的恢复效果及最低信噪比要求，同时比较了在不同条件下算法的精确恢复率，结果可用于某些实际应用场景。

    Jan, 2015

  • RIP 下的正交匹配追踪稀疏恢复

    本文解析了正交匹配追踪算法，表明只需要 O (k̅ln d) 个随机投影，即可恢复一 k̅- 疏松信号的 2 - 范数，从而对于压缩感知应用，该方法比之前的方法所需的随机投影数量 O (k̅²ln d) 更小。

    May, 2010

  • 快速 OMP 用于精确恢复和稀疏逼近

    该论文对 Orthogonal Matching Pursuit (OMP) 进行改进，提出了一种快速算法和一种新的选择准则，从而减少信号恢复所需的迭代次数和计算时间，并给出了精确恢复的充分条件及近似误差的界限。

    Mar, 2024

  • 使用受限等距性质分析正交匹配追踪算法

    使用受限等距性质 (RIP) 分析正交匹配追踪 (OMP) 算法，得出对于任何 K 稀疏信号，RIP 阶数为 K+1 时 (等距常数 δ<1/3K^(1/2)) 足以完全恢复信号。同时，基于 OMP 和满足 RIP 的矩阵之间的简单直觉观察得出信号高度可压缩时，RIP 的放松边界。

    Sep, 2009

  • 均匀不确定性原理和正则化正交匹配追踪信号恢复

    该研究旨在将 L_1 最小化方法和迭代方法（Matching Pursuits）这两种主要的稀疏信号恢复算法方法结合起来。我们提出了一种简单的正则化版本 Orthogonal Matching Pursuit（ROMP），它具有 OMP 的速度和透明性，以及 L_1 最小化的强制统一保证，我们的算法 ROMP 以线性迭代次数（实践中甚至是对数级次数）重构出一个稀疏信号，并且若线性测量满足统一未知原则，则重构是准确的。

    Jul, 2007

  • 通过规则正交匹配追踪实现从不完整和不准确测量中的信号恢复

    本文提出一种简单的贪心算法 ROMP，它结合了贪心方法和凸规划方法的优点，可以从不完整和不准确的测量中可靠地恢复出一个 d 维向量 v，并在最多 n 次迭代中完成对准确稀疏信号的恢复。

    Dec, 2007

  • 随机设计下的高维变量选择和正交匹配追踪

    本文分析了正交匹配追踪（OMP）在随机设计变量选择方面的表现，发现在设计矩阵分布平均后的性能比确定性情况下更加宽松，且对于精确稀疏向量，OMP 的表现类似于 Lasso 算法已有的结果。此外，在更松散的稀疏向量假设下也进行了变量选择分析，从而证明了系数估计满足 strong oracle 类型的不等式。

    Sep, 2011