|
Friday, February 15, 2013 |
|
|
|
|
On Unified View of Nullspace-type Conditions for Sparse and Low-rank Recoveries |
|
|
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. |