Journal
IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING
Volume 4, Issue 2, Pages 310-316Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/JSTSP.2010.2042412
Keywords
Compressed sensing (CS); sparse approximation problem; orthogonal matching pursuit; uncertainty principle
Categories
Funding
- NSF [0652617]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [0918623, 0652617] Funding Source: National Science Foundation
Ask authors/readers for more resources
We demonstrate a simple greedy algorithm that can reliably recover a vector upsilon is an element of R-d from incomplete and inaccurate measurements x =Phi upsilon + e. Here, Phi is a N x d measurement matrix with N << d and is an error vector. Our algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to provide the benefits of the two major approaches to sparse recovery. It combines the speed and ease of implementation of the greedy methods with the strong guarantees of the convex programming methods. For any measurement matrix Phi that satisfies a quantitative restricted isometry principle, ROMP recovers a signal upsilon with O(n) nonzeros from its inaccurate measurements x in at most n iterations, where each iteration amounts to solving a least squares problem. The noise level of the recovery is proportional to root logn parallel to e parallel to(2). In particular, if the error term e vanishes the reconstruction is exact. This stability result extends naturally to the very accurate recovery of approximately sparse signals.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available