On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing

Anatoli Juditsky, Fatma Kilinc Karzan, Arkadii S. Nemirovski

We consider the synthesis problem of Compressed Sensing - given s and an MXn matrix A, extract from it an mXn submatrix A', certified to be s-good, with m as small as possible. Sta…