|
Friday, June 12, 2009 |
|
|
|
|
Verifiable sufficient conditions in Compressed Sensing |
|
|
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, is s-good (i.e., recovers well all sparse signals with at most s nonzero entries) in a surprisingly wide range of the sparsity parameter s. On the other hand, s-goodness of an individual matrix is difficult to verify, and till very recently just one, highly conservative, verifiable sufficient condition for s-goodness was known. In the talk, based on joint research with A. Judistky (Grenoble University) and F. Kilinc Karzan (GaTech), we present novel verifiable sufficient conditions for s-goodness, discuss their relations with the standard difficult to verify conditions, like Restricted Isometry Property, and overview extensions to the case of nonnegative sparse signals. |