Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit
复制标题
DOI：
10.1007/s10208-008-9031-3
复制
发表时间：
2009-06-01
影响因子：
3
通讯作者：
Vershynin, Roman
中科院分区：
文献类型：
--
作者：
Needell, Deanna;Vershynin, Roman
本文旨在桥接两种主要的算法方法，从一组不完整的线性测量值L-1最少方法和迭代方法（匹配的追求）中稀疏信号恢复。我们找到了一种简单的正交匹配追踪（ROMP）的正规化版本，该版本具有两种方法的优点：OMP的速度和透明度以及L-1最小化的强统一保证。我们的算法，romp，在稀疏性的许多迭代中重建一个稀疏的信号，并且如果线性测量值满足统一的不确定性原理，则重建是精确的。
This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements-L-1-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of L-1-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.