Document Type

Article - postprint


Mathematics (CMC)

Publication Date



We demonstrate a simple greedy algorithm that can reliably recover a vector v ?? ??d from incomplete and inaccurate measurements x = ??v + e. Here, ?? is a N x d measurement matrix with Nv 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 ??{logn} ||e||2. In particular, if the error term e vanishes the reconstruction is exact.


2012 IEEE Best Young Author Paper Award

Publisher's PDF can be found at:

Rights Information

© 2010 IEEE

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Included in

Mathematics Commons