On Unified View of Nullspace-type Conditions for Sparse and Low-rank Recoveries
| Speaker: | Fatma Kilinc-Karzan |
|---|---|
| Affiliation: | Carnegie Mellon University |
| Room: | Mathematics and Computer Building (MC) 5158 |
Abstract:
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.