Biomedical Engineering Reference
In-Depth Information
The optimization problem under constraint (
7.3
) can be formulated as a saddle-
point problem for the Lagrangian
L
(
f,λ
)
:
λ
M
||
dx
.
)
||
2
p
)
||
2
p
L
(
f,λ
)=
M
||∇
f
(
x
(
x
)
dx
+
1
−
f
(
x
(
x
)
(7.4)
The Lagrangian (
7.4
) can be rewritten by introducing the weighted Laplacian
operator
=
−
p
div
Δf
(
p
∇
f
)
,
defined on the manifold
M
:
L
(
f,λ
)=
Δf, f
M
+
λ
(1
−
f,f
M
)
.
Setting the derivative of
L
(
f,λ
)
with respect to
f
to zero leads to the eigenvalue
problem
Δf
=
λf
. The constant function
f
cst
equal to
1
everywhere is an
eigenfunction of
Δ
for the eigenvalue
. To avoid this trivial embedding, the solution
f
is constrained to be orthogonal to the function
f
cst
, i.e.,
0
f
(
x
)
p
(
x
)
dx
=0
.
(7.5)
M
The optimal embedding
f
under constraints (
7.3
)-(
7.5
) is the eigenfunction of
Δ
corresponding to the smallest non-zero eigenvalue.
In order to compute
f
from a manifold sampled with a finite number of points,
the operator
Δ
needs to be approximated. Graph Laplacian methods approximate
Δ
through the Laplacian of a particularly designed graph. Let
G
=(
V
,
E
)
be an
undirected graph where
V
are the nodes
(
x
i
)
i
=1
,...,N
and
E
are the edges. A weight
w
ij
is associated to every edge
(
i,j
)
∈E
, leading to a weighted graph
G
.The
Laplacian
L
of the graph is a matrix defined by
L
=
D
−
W
where
W
is the matrix
composed of elements
w
ij
and
D
is diagonal with
D
ii
=
j
w
ij
. The random-
walk Laplacian,
L
rw
, is a normalized version of
L
defined by
L
rw
=
D
−
1
L
=
D
−
1
W
where
I
is the identity.
A weighting matrix
W
allowing a good approximation of
Δ
must now be defined.
This is done with the help of a similarity measure
k
which is a non-increasing
function of the distance
d
X
. Here,
k
is a Gaussian kernel with standard deviation
σ
:
I
−
e
−d
X
(
x
i
,x
j
)
2
/σ
2
.
k
(
x
i
,x
j
)=
In [
12
], the authors proved that the random-walk Laplacian of
converges almost
surely to, the Laplacian operator
Δ
when the sample size
N
goes to infinity, if
G
x
i
,x
j
)
(
d
(
x
i
)
d
(
x
j
))
1
/
2
k
(
w
ij
=
,
(7.6)
)=
i
=1
where
d
(
x
k
(
x, x
i
)
is an estimator of the probability density function over
the manifold
M
.
Search WWH ::
Custom Search