Geoscience Reference
In-Depth Information
Recall
L
is an
(l
u)
matrix. Assuming the vertices are ordered so that the labeled ones
are listed first, we can partition the Laplacian matrix into four sub-matrices
+
u)
×
(l
+
L
ll
,
L
lu
L
=
(5.13)
L
ul
L
uu
(y
1
,...,y
l
)
. Then solving the constrained optimization prob-
lem using Lagrange multipliers with matrix algebra, one can show that the harmonic solution is
partition
f
into
(
f
l
,
f
u
)
, and let
y
l
=
f
l
=
y
l
=−
L
uu
−
1
L
ul
y
l
.
f
u
(5.14)
Example 5.1.
Harmonic Function on Chain Graph
Consider the chain graph in Figure 5.2.
With the natural left-to-right order of vertices, we have
⎡
⎤
⎡
⎤
0100000
1010000
0101000
0010100
0001010
0000101
0000010
1000000
0200000
0020000
0002000
0000200
0000020
0000001
⎣
⎦
⎣
⎦
=
D
=
W
⎡
⎤
(5.15)
100000
−
12
−
10000
0
1
−
⎣
⎦
1000
00
−
12
−
100
000
−
12
−
L
=
10
0000
−
12
−
1
00000
−
12
−
−
11
To apply (5.14), we need to permute the order of vertices to be
(
1
,
7
,
2
,
3
,
4
,
5
,
6
)
so that the labeled
vertices come first. Also note
y
l
=
1
)
. This gives
(
1
,
−
2
,
3
,
1
1
3
,
2
3
f
u
=
3
,
0
,
−
−
(5.16)
for the unlabeled vertices from left to right. It can be thresholded at zero to produce binary labels.
This solution fits our intuition. The magnitude of the solution also coincides with label confidence.
