Graphics Reference
In-Depth Information
d
rs
=
Nb
rr
+
T
s
d
rs
=
2
NT
r
s
When we define
N
2
r
1
N
1
N
1
d
2
·
d
rs
,
d
r
·
=
d
rs
,
d
2
d
rs
s
=
··
=
r
s
s
and using the first equation, we get
1
2
(
d
r
·
+
d
2
·
d
2
d
rs
)
b
rs
=
s
−
··
−
XX
T
, we look for an approxi-
mation. We know from the spectral decomposition that
X
=
Having now calculated
b
rs
and knowing that
B
CD
1
/
2
can be used as an
approximation for
X
, where
C
is the matrix whose columns are the eigenvectors of
B
and
D
1
/
2
is a diagonal matrix with square roots of the eigenvalues on the diagonals.
Looking at the eigenvalues of
B
we decide on a dimensionality
k
lower than that of
d
. Let us say
c
j
are the eigenvectors with
=
λ
j
as the corresponding eigenvalues. Note
that
c
j
is
N
-dimensional. Then we get the new dimension as
z
t
j
λ
j
c
t
j
,
=
j
=
1
,...,
k
,
t
=
1
,...,
N
That is, the new coordinates of instance
t
are given by the
t
th elements of the
eigenvectors,
c
j
,
j
k
, after normalization.
In [
5
], it has been shown that the eigenvalues of
XX
T
=
1
,...,
(
N
×
N
)
are the same as those
of
X
T
X
and the eigenvectors are related by a simple linear transformation.
This shows that PCA does the same work with MDS and does it more easily.
In the general case, we want to find a mapping
z
(
d
×
d
)
k
,
=
g
(
x
|
θ)
, where
z
∈ R
d
, and
g
x
∈ R
(
x
|
θ)
is the mapping function from
d
to
k
dimensions defined up to a
set of parameters
θ
. Classical MDS we discussed previously corresponds to a linear
transformation
W
T
x
z
=
g
(
x
|
W
)
=
but in a general case, nonlinear mapping can also be used: this is called
Sammon map-
ping
. the normalized error in mapping is called the
Sammon stress
and is defined as
z
r
z
s
x
r
x
s
2
(
||
−
|| − ||
−
||
)
E
(θ
|
X
)
=
||
x
r
−
x
s
||
2
r
,
s
x
r
x
s
x
r
x
s
2
(
||
(
|
θ)
−
(
|
θ)
|| − ||
−
||
)
g
g
=
||
x
r
−
x
s
||
2
r
,
s
