  A host of problems involve the recovery of structured signals from a
dimensionality reduced representation such as a random projection; examples
include sparse signals (compressive sensing) and low-rank matrices (matrix
completion). Given the wide range of different recovery algorithms developed to
date, it is natural to ask whether there exist "universal" algorithms for
recovering "structured" signals from their linear projections. We recently
answered this question in the affirmative in the noise-free setting. In this
paper, we extend our results to the case of noisy measurements.
