Orthogonal matching pursuit (OMP) is one of the mainstream algorithms for signal reconstruction/approximation. It plays a vital role in the development of compressed sensing theory, and it also acts as a driving force for the development of other heuristic methods for signal reconstruction. In this paper, we propose the so-called dynamic orthogonal matching pursuit (DOMP) and its two enhanced versions which are more efficient than OMP in signal reconstruction from a numerical point of view, and we provide a rigorous analysis for these algorithms in terms of the restricted isometry property (RIP) of the sensing matrix. The main result claims that the reconstruction error via the proposed algorithms can be controlled and measured with the number of iterations, sparsity level of the signal and the noise level of the measurements. The analysis in this paper sufficiently exploits the structure of the DOMP and an auxiliary convex optimization model (called approximation counterpart) to establish a mild RIP-based performance result for DOMP and its enhanced versions. Dramatically different from existing results for OMP-like algorithms, the results established for the algorithms proposed in this paper do not need any traditional assumptions imposed on the smallest nonzero element of the target signal which is unknown before being actually reconstructed. Moveover, the finite convergence of the algorithms for a class of large-scale compressed sensing problems is also discussed.
翻译:常规匹配追踪(OMP)是信号重建/接近跟踪(OMP)的主流算法之一。 它在开发压缩感测理论中发挥着至关重要的作用, 也是开发其他信号重建方法的驱动力。 在本文中, 我们提出所谓的动态正对匹配追踪(DOMP)及其两个强化版本,它们比OMP在从数字角度进行信号重建时效率更高。 我们从遥感矩阵的限制性等量属性(RIP)的角度对这些算法进行了严格的分析。 其主要结果声称, 通过拟议算法的重建错误可以与信号重建的迭代数、信号的宽度和测量的噪音水平一起加以控制和测量。 本文中的分析充分利用了DOMP的结构以及一个辅助性convex优化模型(所谓的近似对应方), 以便为DOMP及其强化版本建立一个温和的基于RIP的性表现结果。 与OMP类算法的现有结果不同, 主要结果声称, 通过拟议算法的重建错误可以与信号的数量、 信号和测量的噪音水平水平水平相比, 本文中所提出的最不易变的精确的精确的排序假设也需要。 。