On Unified View of Nullspace-type Conditions for Sparse and Low-rank Recoveries
|Affiliation:||Carnegie Mellon University|
|Room:||Mathematics and Computer Building (MC) 5158|
We discuss a general notion of ~Ssparsity structure~T and present a unified framework for the recovery of "sparse-structured" signals from their linear image of reduced dimension possibly corrupted with noise. This unified treatment covers usual sparse and block-sparse recoveries via commonly used $\ell_1$ regularization as well as low-rank matrix reconstruction via nuclear norm minimization. We present null-space type sufficient conditions for the recovery to be precise in the noiseless case, derive error bounds for imperfect recovery (nearly sparse signal, presence of observation noise) and relate to the other well-known conditions (Restricted Isometry Property, Mutual Incoherence) from the literature. Our emphasis is on efficiently verifiable sufficient conditions on the problem parameters (sensing matrix and sparsity structure) for the validity of the associated nullspace properties. While the efficient verifiability of a condition is by no means necessary for the condition to be meaningful and useful, we believe that verifiability has its value and is worthy of being investigated. In particular, verifiability allows us to design new recovery routines with explicit confidence bounds for the recovery error, which can then be optimized over the method parameters leading to recovery procedures with improved statistical properties.
Parts of this are joint work with Anatoli Juditsky, Arkadi Nemirovski and Boris Polyak.
200 University Avenue West
Waterloo, ON N2L 3G1