Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit |
| |
Authors: | Deanna Needell Roman Vershynin |
| |
Institution: | (1) Department of Mathematics, University of California, One Shields Ave, Davis, CA 95616, USA |
| |
Abstract: | This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear
measurements—L1-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 L1-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.
|
| |
Keywords: | Signal recovery algorithms Restricted isometry condition Uncertainty principle Basis pursuit Compressed sensing Orthogonal matching pursuit Signal recovery Sparse approximation |
本文献已被 SpringerLink 等数据库收录! |