Biomedical Engineering Reference
In-Depth Information
model selection problem. Section 5 summarizes various interesting nd-
ings/ideas that have been published recently | for obvious reasons, we
give an emphasis on publications that come after the two survey papers
mentioned at the beginning of this article.
2. Our Perspective
We consider two types of optimization problems:
one optimization problem that is based on a counting measure,
kyxk
2
+
0
kxk
0
;
(P0)
min
x
R
n
, notationkk
2
denotes the sum of
squares of the entries of a vector, constant
0
0 is an algorithmic
parameter, and quantitykxk
0
is the number of nonzero entries in
vector x;
one optimization problem that depends on a sum of absolute values,
R
nm
; x2
R
m
; y2
where 2
kyxk
2
+
1
(P1)
min
x
kxk
1
;
P
m
i=1
jfor vector x = (x
1
; x
2
; : : : ; x
m
)
T
, and con-
stant
1
0 is another algorithmic parameter whose role will be
discussed later.
wherekxk
1
=
jx
i
1
) is a quasi-norm (respectively, norm) in
R
m
. In the literature of sparse signal presentation, they are called `
0
-norm
and `
1
-norm, respectively. The numbers \0" and \1" in the notations (P0)
and (P1) follow such a convention in Donlho and Huo
11
, Donoho, et al.
10
,
and Chen and Huo
4;5
.
Model selection in regression is equivalent to subset selection. In subset
selection under linear regression, many well known criteria { including C
p
statistic, Akaike information criterion (AIC), Bayesian information criterion
(BIC), minimum description length (MDL), risk ination criterion (RIC),
and so on | are special cases of (P0), by assigning dierent values to
0
. Details regarding the foregoing statement will be provided later. It is
shown that problem (P0) in general is NP-hard (Theorem 1; also see Huo
and Ni
28
).
On the other hand, (P1) is the mathematical problem that is called
upon in Lasso
47
. Recent advances (whose details and references are pro-
vided in Section 3.2) demonstrate that some stepwise algorithms (e.g., least
angle regressions (LARS) presented in Efron, et al.
14
) reveal the solution
Notekxk
0
(respectively,kxk
Search WWH ::
Custom Search