Digital Signal Processing Reference
In-Depth Information
parameter is an important topic in statistical signal processing, and here we provide
some guidelines.
BPDN Asymptotics
In the statistical community, many authors have studied consistency and correct
sparsity recovery properties of BPDN (Lasso); see, for example, Meinshausen and
B uhlmann (2006), Bickel et al. (2009), Wainwright (2009), and Cand es and Plan
(2009), and references therein. These works established that if the regularization
parameter is set to
2
λ
=
τσ
ε
2log
T
(7.33)
2
√
2), then BPDN can recover the correct sparsity pattern
or be consistent with the original sparse vector under additional conditions on
F
(e.g., incoherence, appropriate spectrum). This choice of
for large enough
τ
(
τ>
was also advocated by
Chen et al. (1999), as inspired by the universal threshold that we discussed in Sec-
tion 6.2.2.4 in the orthogonal case.
λ
Heuristics
In his attempt to solve the constrained form of the (discrete) total variation de-
noising, Chambolle (2004) devised a sequence of regularized problems each with
a different value of
λ
. To meet a constraint size
σ
, an intuitive update of the
λ
is
λ
. The theoretical analysis is rigorous for denoising. In
practice, it was observed by Chambolle (2004) that this rule still works when
=
λ
σ/
residuals
old
new
old
is
updated at each step of the algorithm solving the regularized problem, and even
with inverse problems. Transposed to our setting, for a given target size of the resid-
uals
λ
σ
, the update rule reads
(
t
)
λ
t
+
1
=
λ
t
σ/
y
−
H
α
.
(7.34)
The reader must, however, avoid concluding that this procedure solves (
P
2
σ
) exactly.
Cross-Validation
Dupe et al. (2009) propose to objectively select the regularizing parameter
based
on an adaptive model selection criterion such as the generalized cross-validation
(GCV) (Golub et al. 1979). GCV attempts to provide a data-driven estimate of
λ
λ
by
minimizing
y
)
2
α
(
y
;
−
H
λ
GCV(
λ
)
=
,
(7.35)
(
m
−
df
)
2
α
(
y
;
where
and
df
is
the effective number of degrees of freedom. Unlike Tikhonov regularization, where
df
is the trace of the so-called influence or hat matrix, deriving the closed-form
expression of
df
is challenging for BPDN.
SURE theory (Stein 1981) gives a rigorous definition of
df
for any fitting pro-
cedure. Let
y
(
y
;
λ
) denotes the solution to BPDN for the observation
y
using
λ
λ
=
α
(
y
;
λ
)
H
) represent the model fit from
y
. As the noise
2
This value must be multiplied by the
2
norm of each column of
F
if the latter is not normalized.
