TITLE: Verifiable sufficient conditions for good L1-recovery in Compressed Sensing

SPEAKER: Dr. Arkadi Nemirovski

ABSTRACT:

Compressed Sensing is a rapidly developing novel area in Signal Processing aimed at recovering sparse high-dimensional signals from their low-dimensional linear images, or, which is the same, recovering sparse solutions to heavily underdetermined systems of linear equations. The standard recovery algorithm in this context is L1 minimization, where we estimate the true signal by choosing among the solutions to the system the one with the minimal L1 norm. Theory says that when the matrix of the system is picked at random, such a procedure, with overwhelming probability, recovers true sparse signals in a surprisingly wide range of the sparsity parameter. At the same time, until very recently no computationally tractable sufficient conditions for a matrix to allow for good L1 recovery of signals of given sparsity were known. In the talk, based on joint research with A. Judistky (Grenoble University) and F. Kilinc Karzan (ISyE), we present and discuss conditions of this type along with their relations with the standard difficult to verify conditions, like Restricted Isometry Property.