Biomedical Engineering Reference
In-Depth Information
TaBlE 4.4:
Procedure of the LAR algorithm
Given an
N
×
M
input matrix
X
(each row being
M
-dimensional sample vector), and an
N
× 1
desired response matrix
y
, initialize the model coefficient
β
i
= 0, for
i
= 1,… ,
M
,
and let
β
= [
β
1
, … ,
β
M
]
T
Then the initial LAR estimate becomes
Y X
=
= 0
.
Transform
X
and
y
such that
1
N
1
N
1
N
å
=
,
å
=
,
å
=
, for
j
= 1,… ,
M
.
2
x
ij
0
x
ij
1
y
i
0
N
N
N
i
=
1
i
=
1
i
=
1
ˆ
T
a) Compute the current correlation
c
=
X
(
Y
−
Y
)
c
{ }
, and a set A = [
j
: |
c
j
| =
C
max
].
c) Let
X
a
= [… , sign(
c
j
)
x
j
, …] for
j
∈ A.
d) Let Φ =
X
a
T
X
a
, and α = (
1
a
T
Φ
−1
1
a
)
−1
, where
1
a
is a vector of 1's with a length equal to size of
A
.
e) Compute the equiangular vector µ =
X
a
(αΦ
−1
1
a
) that has the unit length. Note that that
X
a
µ = α
1
a
(angles between all inputs in
A
and µ are equal).
f ) Compute the step size,
b) Find
C
max
=
max
j
j
C
−
−
c C
+
+
c
max
j
max
j
+
γ
=
min
,
C
j A
∈
α θ
α θ
j
j
where min
+
indicates considering only positive minimum values over possible
j
.
g) Compute θ
j
, which is defined as the inner product between all inputs and µ such as,
θ
j
=
X
T
µ
h) Update
Ŷ
+
=
Ŷ +
γµ.
Repeat a-h until all inputs join the active set A, or
exceeds the given threshold.
∑
β
j
j
vector in this direction as computed in Table
4.4
(e). The amount of movement along
μ
1
, denoted as
γ
1
, is computed by equation in Table
4.4
(f ).
y
1
denotes the OLS estimate of desired response
y
with
input
x
1
. Note that the estimate by LAR (
ŷ
1
) moves toward
y
1
, but does not reach it. The next direc-
tion
μ
2
intersects the angle between
x
1
and
x
2
(equiangular vector in the 2D space of
x
1
and
x
2
) such
that the angle between
x
1
and the updated residual (
r
1
=
y
2
- γ
1
μ
1
) is same as the one between
x
2
and
r
1
.
Because every input is standardized such that the correlation that is measured by the inner product of
x
1
and
x
2
can be estimated by the angle between
x
1
and
x
2
, these two variables have the same absolute
correlation with
r
1
following the equation in Table
4.4
(a). The coefficient γ
2
is computed again follow-
ing Table
4.4
(f ), such that
x
3
has the same absolute correlation with the next residual
r
2
=
y
3
- (γ
1
μ
1
+
γ
2
μ
2
) as
x
1
and
x
2
. So, the next direction
μ
3
intersects the angle between
x
1
,
x
2
, and
x
3
. This procedure
is repeated until the
L
1
norm of coefficients reaches a given threshold.
LAR can be easily modified to implement LASSO; when some coefficients cross zero at a
given step, those are forced to be zero. And the corresponding inputs are removed from the selected
