Digital Signal Processing Reference
In-Depth Information
Figure 11.2. Geometry of recovery by
1
minimization for
N
= 2 and
m
= 1. (left) The
2
minimal solution is not sparse. (middle) The BP solution recovers the sparse solution exactly.
(right) Solution of (P
2
) when noise is present in the measurements.
α
in
are known, then the simplified problem can be solved by least squares provided
m
k
. This is, in turn, equivalent to imposing that any submatrix of
k
columns ex-
tracted from
F
is well conditioned. This introduces the so-called restricted isometry
property (RIP), which plays a fundamental role in the study of the recovery proper-
ties of compressed sensing. The RIP imposes that there exists a 0
≥
<δ
s
<
1 such that
N
with
for any
α
∈ R
α
0
≤
k
(Candes and Tao 2005),
2
2
2
(1
−
δ
k
)
α
≤
F
α
≤
(1
+
δ
k
)
α
.
(11.5)
Variable
δ
s
is called the restricted isometry constant (RIC).
F
satisfies the RIP of or-
der
k
if the RIC
δ
k
is not too close to 1. In plain language, the matrix
F
approximately
preserves the lengths of
k
-sparse vectors, implying that
k
-sparse vectors cannot be
in the null-space of
F
. The RIP is also closely related to the incoherence property
discussed earlier. Recently, analysis of CS involving an asymmetric version of the
RIP has appeared; see Foucart and Lai (2009) and Blanchard et al. (2009).
Of course, the locations of the
k
nonzero entries in
α
are not known in general.
In such a setting, it is sufficient to require that
δ
2
k
<
1 to recover
α
from
y
=
F
α
.To
see this, let
α
be the unique sparsest solution, and consider any other solution
α
+
ζ
,
with
ζ
in the null-space of
F
. Thus, because
F
ζ
=
0 and
F
satisfies the RIP of order
2
k
,
ζ
is at least (2
k
+
1)-sparse. In turn, this implies that any other solution
α
+
ζ
is
at least (
k
is unique. Hence, to recover
k
-sparse
signals, the lower bound in equation (11.5) plays an important role. In the following
section, we will see that the RIP not only guarantees recovery by
+
1)-sparse; that is, the solution
α
1
minimization
(exact for sparse and accurate for compressible signals), but also stability to noise.
11.4.2 Stability to Compressibility and Noise
For the CS to be widely applicable, the recovery process needs to be stable in the
sense that small perturbations in the observed data should induce small perturba-
tions in the reconstruction. Suppose now that the observed measurements are noisy
according to equation (7.1), with
ε
≤
σ
. Because of inaccurate measurements, CS
proposes to solve the
1
-regularized noise-aware variant (7.5). The latter can again
be solved efficiently using the splitting methodology developed in Section 7.4.2.
