Robust Signal Recovery from Incomplete Observations

Recently, a series of exciting results have shown that it is possible to reconstruct a sparse signal exactly from a very limited number of linear measurements by solving a convex optimization program. If our underlying signal f can be written as a superposition of B elements from a known basis, it is possible to recover f from a projection onto a generic subspace of dimension about B log N. Moreover, the procedure is robust to measurement error; adding a perturbation of size ∈ to the measurements will not induce a recovery error of more than a small constant times ∈. In this paper, we will briefly overview these results, and show how the recovery via convex optimization can be implemented in an efficient manner, and present some numerical results illustrating the practicality of the procedure.