  We demonstrate a simple greedy algorithm that can reliably recover a
d-dimensional vector v from incomplete and inaccurate measurements x. Here our
measurement matrix is an N by d matrix with N much smaller than d. Our
algorithm, Regularized Orthogonal Matching Pursuit (ROMP), seeks to close the
gap between 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 that satisfies a Uniform
Uncertainty Principle, ROMP recovers a signal 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 the norm of the error, up to a log factor. In particular, if
the error vanishes the reconstruction is exact. This stability result extends
naturally to the very accurate recovery of approximately sparse signals.
