# Nonlinear Alignment and Its Local Linear Iterative Solution

Authors: Sumin Zhang; Zhengming Ma; Zengrong Zhan
Journal: Mathematical Problems in Engineering
 (2016)

---

## Abstract

In manifold learning, the aim of alignment is to derive the global coordinate of manifold from the local coordinates of manifold’s patches. At present, most of manifold learning algorithms assume that the relation between the global and local coordinates is locally linear and based on this linear relation align the local coordinates of manifold’s patches into the global coordinate of manifold. There are two contributions in this paper. First, the nonlinear relation between the manifold’s global and local coordinates is deduced by making use of the differentiation of local pullback functions defined on the differential manifold. Second, the method of local linear iterative alignment is used to align the manifold’s local coordinates into the manifold’s global coordinate. The experimental results presented in this paper show that the errors of noniterative alignment are considerably large and can be reduced to almost zero within the first two iterations. The large errors of noniterative/linear alignment verify the nonlinear nature of alignment and justify the necessity of iterative alignment.


---

## Body

## 1. Introduction

Several papers published in Science in 2000 started the research on manifold learning [1, 2]. From then on, manifold learning has made great progress and produced many representative algorithms as well as a lot of improvements around these representative algorithms, such as ISOMAP [2], Locally Linear Embedding (LLE) [1, 3], Hessian LLE (HLLE) [4], Local Tangent Space Alignment (LTSA) [5], Laplacian Eigenmaps (LE) [6], Diffusion Maps [7], and Maximum Variance Unfolding (MVU) [8]. Manifold learning as a way of machine learning has achieved good performance in many applications of machine learning.It may be worth noting that although many machine learning algorithms claim to be manifold learning algorithms, they seem to have nothing to do with the topological manifolds defined in mathematics, not to mention the differential manifolds. The manifold learning algorithm proposed in this paper is based on the mathematical characteristics of topological/differential manifolds. This kind of algorithms can be divided into two stages: local homeomorphism and alignment. The mathematical foundation of local homeomorphism is based on the definition of topological manifolds, while the mathematical foundation of alignment is based on the characteristics of differential manifolds. In local homeomorphism, a manifold is divided into a finite number of overlapped local regions. Each local region is homeomorphic to an open set of Euclidean space. The local regions are called patches of manifold and the open sets homeomorphic to the patches are called local coordinates of patches or local coordinates of manifold directly. In alignment, the local coordinates are aligned in Euclidean space to form an area corresponding to the manifold. The area is called global coordinate of manifold. This paper only focuses on alignment; that is to say, we assume that the local coordinates have already been obtained during local homeomorphism and under this assumption we only study how to derive global coordinates from local coordinates.The remaining sections are arranged as follows. In Section2, some related works are reviewed briefly. In Section 3, the mathematical foundations of manifold learning are laid. In Section 4, the local nonlinear relation between the global and local coordinates is deduced mathematically. In Section 5, the local linear iterative alignment (LLIA) solution to nonlinear alignment is proposed. In Section 6 the experimental results are presented. In Section 7, some conclusions are given.


## 2. Related Works

There are three kinds of alignment in manifold learning: local coordinate alignment, patch alignment, and manifold alignment. The alignment in the algorithm proposed in this paper belongs to local coordinate alignment.The local coordinate alignment is based on the mathematical definition of manifold. According to the mathematical definition of manifold, a manifold can be divided into a number of overlapped patches and each patch is homeomorphic to an open set of Euclidean space. The open sets are called local coordinates of manifold. The local coordinate alignment is to align the local coordinates in Euclidean space to form a larger open set which will be correspondent to the manifold globally. This larger open set is called global coordinate of manifold. The local coordinate alignment can be done by aligning local coordinates one by one on the light of geometrical intuition [9–11] or by turning alignment into an eigenvalue-solving problem with differential geometry [5, 12–15].The patch alignment [16] is more algebraic than geometrical. Before alignment, the given data X
=
x
1
,
…
,
x
N have to be divided into overlapped patches X
n
=
x
n
1
,
…
,
x
n
K
⊆
X, n
=
1
,
…
,
N. The patch alignment is then formulated as follows:(1)
Y
∗
=
arg
min
Y
⁡
∑
n
=
1
N
t
r
a
c
e
Y
L
n
Y
T
,where L
n is called local pattern of X
n, n
=
1
,
…
,
N. How to calculate L
n from X
n is dependent on different algorithms. For example, in LE algorithm [6],(2)
∑
k
=
1
K
ω
n
,
n
k
y
n
-
y
n
k
2
=
∑
k
=
1
K
ω
n
,
n
k
Y
s
n
k
2
=
∑
k
=
1
K
ω
n
,
n
k
t
r
a
c
e
Y
s
n
k
s
n
k
T
Y
T
=
t
r
a
c
e
Y
∑
k
=
1
K
ω
n
,
n
k
s
n
k
s
n
k
T
Y
T
=
t
r
a
c
e
Y
L
n
Y
T
,where ω
n
,
n
k
=
e
-
x
n
-
x
n
k
2
/
2
σ
2 is the similarity between x
n and x
n
k, L
n
=
∑
k
=
1
K
ω
n
,
n
k
s
n
k
s
n
k
T and s
n
k
∈
R
N such that the n
t
h and n
k
t
h components of s
n
k are 1 and -
1, respectively; the other components are 0. More complicated schemes to calculate L
n based on the local similarity, local linearity, local geometry, and so on in X
n can be found in [17–19].In supervised or semisupervised learning, besides the inherent attributes of data; there are discriminative labels assigned to data. Many recent researches in patch alignment try to incorporate the discriminative labels into the calculation ofL
n. For example, in MPA algorithm [20], the neighbours of x
n are first divided into two groups: x
n
1
w
,
…
,
x
n
K
1
w have the same label with x
n, while x
n
1
b
,
…
,
x
n
K
2
b have different labels from x
n or have no label at all; then (3)
∑
k
=
1
K
1
ω
n
,
n
k
w
y
n
-
y
n
k
w
2
-
β
∑
k
=
1
K
2
ω
n
,
n
k
b
y
n
-
y
n
k
b
2
=
t
r
a
c
e
Y
L
n
w
Y
T
-
β
t
r
a
c
e
Y
L
n
b
Y
T
=
t
r
a
c
e
Y
L
n
Y
T
,where L
n
w
=
∑
k
=
1
K
1
ω
n
,
n
k
w
s
n
k
w
s
n
k
w
T, L
n
b
=
∑
k
=
1
K
2
ω
n
,
n
k
b
s
n
k
b
s
n
k
b
T
,
L
n
=
L
n
w
-
β
L
n
b. More schemes in this respect can be founded in [20, 21].The manifold alignment is involved in a number of high-dimensional datasets which are taken from different manifolds. These datasets are all reduced to a low-dimensional Euclidean space and aligned according to certain rules. For example, letX
f
=
x
1
f
,
…
,
x
N
f
f and X
g
=
x
1
g
,
…
,
x
N
g
g be two different datasets and let Y
f
=
y
1
f
,
…
,
y
N
f
f and Y
g
=
y
1
g
,
…
,
y
N
g
g be the results of dimension reduction of X
f and X
g; then the framework of LE-like manifold alignment can be expressed as follows:(4)
arg
min
Y
f
,
Y
g
⁡
∑
i
=
1
N
f
∑
k
=
1
N
f
ω
i
,
j
f
y
i
f
-
y
j
f
2
+
∑
i
=
1
N
g
∑
k
=
1
N
g
ω
i
,
j
g
y
i
g
-
y
j
g
2
+
∑
i
=
1
N
f
∑
k
=
1
N
g
ω
i
,
j
f
,
g
y
i
f
-
y
j
g
2
,where ω
i
,
j
f is the similarity between y
i
f and y
j
f, ω
i
,
j
g the similarity between y
i
g and y
j
g, and ω
i
,
j
f
,
g the similarity between y
i
f and y
j
g. If y
i
f and y
j
g are not matching points between X
f and X
g, ω
i
,
j
f
,
g
=
0. How to determine the matching points and how to calculate the similarity are application-dependent. More complicated manifold learning algorithms can be founded in [22–27].


## 3. Mathematical Foundations of Manifold Learning

Manifold learning can be divided into two stages: local homeomorphism and alignment. In this section we will elaborate the mathematical foundations of local homeomorphism and alignment.


### 3.1. Mathematical Foundations of Local Homeomorphism

LetM be a Hausdorff topological space; if, for all x
∈
M, there is a neighbourhood X
x
⊆
M of x such that X
x is homeomorphic to an open set Θ
x of d-dimensional Euclidean space R
d, then M is called an d-dimensional topological manifold (see Figure 1). Now let φ
x
:
X
x
→
Θ
x be the homeomorphic mapping between X
x and Θ
x; X
x
,
φ
x is called a chart of M and X
x
,
φ
x
∣
x
∈
M is called an atlas of M.Figure 1
Definition of topological manifolds,X
x is the neighbourhood of x, Θ
x is an open set in R
d, and φ
x is a homeomorphic mapping between X
x and Θ
x.In manifold learning, the neighbourhoodX
x is called a patch of M and the open set Θ
x
=
φ
x
X
x is called the local coordinate of X
x. Furthermore, let Θ
~
x
=
Θ
x
-
φ
x
x and φ
~
x
:
X
x
→
Θ
~
x such that for all x
′
∈
X
x, φ
~
x
x
′
=
φ
x
x
′
-
x. It is clear that φ
~
x is also a homeomorphic mapping between X
x and another open set Θ
~
x. An important feature of φ
~
x which will facilitate the mathematical deduction of nonlinear alignment is that φ
~
x
x
=
0. Hereafter, all the local homeomorphic mappings used in this paper are assumed to have this feature.Furthermore, the setX
x
∣
x
∈
M is an open cover of M; that is, M
=
⋃
x
∈
M
X
x. If M is compact, then there must be a finite subset of X
x
∣
x
∈
M such that this finite subset is also an open cover of M [28]. More specifically, if M is a d-dimensional compact manifold, then there must be a finite number of points x
1
,
…
,
x
N and the corresponding neighbourhoods X
1
,
…
,
X
N such that(1)
X
n is homeomorphic to an open set Θ
n of d-dimensional Euclidean space R
d, n
=
1
,
…
,
N.
(2)
X
1
,
…
,
X
N is a finite open cover of M; that is, M
=
⋃
n
=
1
N
X
n.In practice, the given datax
1
,
…
,
x
N are always assumed to be taken from a compact manifold M and have the neighbourhoods X
1
,
…
,
X
N which are locally homeomorphic to the open sets Θ
1
,
…
,
Θ
N of Euclidean space. The aim of manifold learning during the stage of local homeomorphism is to find these neighbourhoods X
1
,
…
,
X
N and then derive the local coordinates Θ
1
,
…
,
Θ
N of these neighbourhoods. It is clear that the existence of the neighbourhoods and their local coordinates is guaranteed by the mathematical definition of topological manifold. At present, the most commonly used method of finding the neighbourhoods is theK Nearest Neighbours (KNN) method and the most commonly used method of deriving the local coordinates of neighbourhoods is the so-called tangent space method, that is, the local PCA method [5, 29].


### 3.2. Mathematical Foundations of Alignment

LetM be a topological manifold and X
x
,
φ
x
∣
x
∈
M an atlas of M; if, for any two charts X
x
,
φ
x and X
z
,
φ
z such that X
x
∩
X
z
≠
⌀, the mapping φ
z
∘
φ
x
-
1
:
φ
x
X
x
∩
X
z
→
φ
z
X
x
∩
X
z is C
∞ differentiable, then M is called C
∞ differential manifold (see Figure 2). In the rest part of this paper the manifolds are all assumed to be C
∞ differential manifolds.Figure 2
Definition of differential manifolds:X
x
,
φ
x and X
z
,
φ
z are two charts, X
x
∩
X
z
≠
⌀, and M is said to be C
∞ differentiable if φ
z
∘
φ
x
-
1 is C
∞ differentiable.Letf
:
M
→
R be a function defined on the differential manifold M. Generally speaking, f cannot be differentiated directly on M. In order to define the differentiability of f on M, we have to define its local pullback function first. Now let x
∈
M. According to the definition of manifold, there must be a neighbourhood X
x
⊆
M of x such that X
x is homeomorphic to an open set Θ
x of Euclidean space R
d, where d is the dimension of M. Let φ
x
:
X
x
→
Θ
x be the homeomorphic mapping between X
x and Θ
x, the so-called local pullback function of f is then defined as f
x
=
f
∘
φ
x
-
1
:
Θ
x
→
R (see Figure 3).Figure 3
The Local Pullback of functions defined on manifolds;f is defined on X
x and f
∘
φ
x
-
1 is defined on Θ
x. Since X
x and Θ
x are homeomorphic, the differentiation of f on X
x can be defined by using the differentiation of its pullback function f
∘
φ
x
-
1 on Θ
x.Note that, in the theory of topological spaces, being homeomorphic means being identical. Also note that manifold is a kind of topological space. Therefore, when limited within the local regionsX
x and Θ
x, f can be regarded as the same with its local pullback function f
x
=
f
∘
φ
x
-
1.Furthermore, according to the definition of differential manifold, ifM is C
∞ differentiable, so is the function φ
z
∘
φ
x
-
1. Therefore, if the function φ
z is replaced with f in φ
z
∘
φ
x
-
1, then the differentiability of f
∘
φ
x
-
1 is completely dependent on f. This is the reason why the differentiability of f within the local region X
x is defined by the differentiability of its local pullback function f
x
=
f
∘
φ
x
-
1 within the local region Θ
x. More specifically, by making use of φ
x
x
=
0, that is, x
=
φ
x
-
1
0, the gradient vector and Hessian matrix of f at x can be expressed as follows:(5)
∇
f
x
=
∇
f
φ
x
-
1
0
=
∇
f
∘
φ
x
-
1
0
=
∇
f
x
0
=
∂
f
x
ρ
∂
ρ
1
⋮
∂
f
x
ρ
∂
ρ
d
ρ
=
0
,
H
f
x
=
H
f
φ
x
-
1
0
=
H
f
∘
φ
x
-
1
0
=
H
f
x
0
=
∂
2
f
x
ρ
∂
ρ
1
∂
ρ
1
⋯
∂
2
f
x
ρ
∂
ρ
1
∂
ρ
d
⋮
⋱
⋮
∂
2
f
x
ρ
∂
ρ
d
∂
ρ
1
⋯
∂
2
f
x
ρ
∂
ρ
d
∂
ρ
d
ρ
=
0
.Iff is C
∞ differentiable, f can be even Taylor-expanded in the neighbourhood of x. In fact, for all x
′
∈
X
x, (6)
f
x
′
=
f
φ
x
-
1
∘
φ
x
x
′
=
f
∘
φ
x
-
1
φ
x
x
′
=
f
x
θ
′
=
f
x
0
+
∇
f
x
0
T
θ
′
+
1
2
θ
′
T
H
f
x
0
θ
′
+
⋯
=
f
x
+
∇
f
x
T
θ
′
+
1
2
θ
′
T
H
f
x
θ
′
+
⋯
,where θ
′
=
φ
x
x
′
∈
Θ
x. The differentiation of local pullback functions lays the mathematical foundation of alignment.


## 3.1. Mathematical Foundations of Local Homeomorphism

LetM be a Hausdorff topological space; if, for all x
∈
M, there is a neighbourhood X
x
⊆
M of x such that X
x is homeomorphic to an open set Θ
x of d-dimensional Euclidean space R
d, then M is called an d-dimensional topological manifold (see Figure 1). Now let φ
x
:
X
x
→
Θ
x be the homeomorphic mapping between X
x and Θ
x; X
x
,
φ
x is called a chart of M and X
x
,
φ
x
∣
x
∈
M is called an atlas of M.Figure 1
Definition of topological manifolds,X
x is the neighbourhood of x, Θ
x is an open set in R
d, and φ
x is a homeomorphic mapping between X
x and Θ
x.In manifold learning, the neighbourhoodX
x is called a patch of M and the open set Θ
x
=
φ
x
X
x is called the local coordinate of X
x. Furthermore, let Θ
~
x
=
Θ
x
-
φ
x
x and φ
~
x
:
X
x
→
Θ
~
x such that for all x
′
∈
X
x, φ
~
x
x
′
=
φ
x
x
′
-
x. It is clear that φ
~
x is also a homeomorphic mapping between X
x and another open set Θ
~
x. An important feature of φ
~
x which will facilitate the mathematical deduction of nonlinear alignment is that φ
~
x
x
=
0. Hereafter, all the local homeomorphic mappings used in this paper are assumed to have this feature.Furthermore, the setX
x
∣
x
∈
M is an open cover of M; that is, M
=
⋃
x
∈
M
X
x. If M is compact, then there must be a finite subset of X
x
∣
x
∈
M such that this finite subset is also an open cover of M [28]. More specifically, if M is a d-dimensional compact manifold, then there must be a finite number of points x
1
,
…
,
x
N and the corresponding neighbourhoods X
1
,
…
,
X
N such that(1)
X
n is homeomorphic to an open set Θ
n of d-dimensional Euclidean space R
d, n
=
1
,
…
,
N.
(2)
X
1
,
…
,
X
N is a finite open cover of M; that is, M
=
⋃
n
=
1
N
X
n.In practice, the given datax
1
,
…
,
x
N are always assumed to be taken from a compact manifold M and have the neighbourhoods X
1
,
…
,
X
N which are locally homeomorphic to the open sets Θ
1
,
…
,
Θ
N of Euclidean space. The aim of manifold learning during the stage of local homeomorphism is to find these neighbourhoods X
1
,
…
,
X
N and then derive the local coordinates Θ
1
,
…
,
Θ
N of these neighbourhoods. It is clear that the existence of the neighbourhoods and their local coordinates is guaranteed by the mathematical definition of topological manifold. At present, the most commonly used method of finding the neighbourhoods is theK Nearest Neighbours (KNN) method and the most commonly used method of deriving the local coordinates of neighbourhoods is the so-called tangent space method, that is, the local PCA method [5, 29].


## 3.2. Mathematical Foundations of Alignment

LetM be a topological manifold and X
x
,
φ
x
∣
x
∈
M an atlas of M; if, for any two charts X
x
,
φ
x and X
z
,
φ
z such that X
x
∩
X
z
≠
⌀, the mapping φ
z
∘
φ
x
-
1
:
φ
x
X
x
∩
X
z
→
φ
z
X
x
∩
X
z is C
∞ differentiable, then M is called C
∞ differential manifold (see Figure 2). In the rest part of this paper the manifolds are all assumed to be C
∞ differential manifolds.Figure 2
Definition of differential manifolds:X
x
,
φ
x and X
z
,
φ
z are two charts, X
x
∩
X
z
≠
⌀, and M is said to be C
∞ differentiable if φ
z
∘
φ
x
-
1 is C
∞ differentiable.Letf
:
M
→
R be a function defined on the differential manifold M. Generally speaking, f cannot be differentiated directly on M. In order to define the differentiability of f on M, we have to define its local pullback function first. Now let x
∈
M. According to the definition of manifold, there must be a neighbourhood X
x
⊆
M of x such that X
x is homeomorphic to an open set Θ
x of Euclidean space R
d, where d is the dimension of M. Let φ
x
:
X
x
→
Θ
x be the homeomorphic mapping between X
x and Θ
x, the so-called local pullback function of f is then defined as f
x
=
f
∘
φ
x
-
1
:
Θ
x
→
R (see Figure 3).Figure 3
The Local Pullback of functions defined on manifolds;f is defined on X
x and f
∘
φ
x
-
1 is defined on Θ
x. Since X
x and Θ
x are homeomorphic, the differentiation of f on X
x can be defined by using the differentiation of its pullback function f
∘
φ
x
-
1 on Θ
x.Note that, in the theory of topological spaces, being homeomorphic means being identical. Also note that manifold is a kind of topological space. Therefore, when limited within the local regionsX
x and Θ
x, f can be regarded as the same with its local pullback function f
x
=
f
∘
φ
x
-
1.Furthermore, according to the definition of differential manifold, ifM is C
∞ differentiable, so is the function φ
z
∘
φ
x
-
1. Therefore, if the function φ
z is replaced with f in φ
z
∘
φ
x
-
1, then the differentiability of f
∘
φ
x
-
1 is completely dependent on f. This is the reason why the differentiability of f within the local region X
x is defined by the differentiability of its local pullback function f
x
=
f
∘
φ
x
-
1 within the local region Θ
x. More specifically, by making use of φ
x
x
=
0, that is, x
=
φ
x
-
1
0, the gradient vector and Hessian matrix of f at x can be expressed as follows:(5)
∇
f
x
=
∇
f
φ
x
-
1
0
=
∇
f
∘
φ
x
-
1
0
=
∇
f
x
0
=
∂
f
x
ρ
∂
ρ
1
⋮
∂
f
x
ρ
∂
ρ
d
ρ
=
0
,
H
f
x
=
H
f
φ
x
-
1
0
=
H
f
∘
φ
x
-
1
0
=
H
f
x
0
=
∂
2
f
x
ρ
∂
ρ
1
∂
ρ
1
⋯
∂
2
f
x
ρ
∂
ρ
1
∂
ρ
d
⋮
⋱
⋮
∂
2
f
x
ρ
∂
ρ
d
∂
ρ
1
⋯
∂
2
f
x
ρ
∂
ρ
d
∂
ρ
d
ρ
=
0
.Iff is C
∞ differentiable, f can be even Taylor-expanded in the neighbourhood of x. In fact, for all x
′
∈
X
x, (6)
f
x
′
=
f
φ
x
-
1
∘
φ
x
x
′
=
f
∘
φ
x
-
1
φ
x
x
′
=
f
x
θ
′
=
f
x
0
+
∇
f
x
0
T
θ
′
+
1
2
θ
′
T
H
f
x
0
θ
′
+
⋯
=
f
x
+
∇
f
x
T
θ
′
+
1
2
θ
′
T
H
f
x
θ
′
+
⋯
,where θ
′
=
φ
x
x
′
∈
Θ
x. The differentiation of local pullback functions lays the mathematical foundation of alignment.


## 4. Nonlinear Alignment

In manifold learning, it is always assumed that and-dimensional manifold M can be mapped to an open set Π of the d-dimensional Euclidean space R
d. The open set Π is called the global coordinate of M. The global coordinate of a manifold is the target of manifold learning. The aim of alignment is to derive the manifold’s global coordinate from its local coordinates.Now letφ
:
M
→
Π be the mapping between the manifold M and its global coordinate Π. For all x
∈
M, y
=
φ
x
=
φ
1
x
⋯
φ
d
x
T
∈
Π
⊆
R
d is also called the global coordinate of x, where φ
i
:
M
→
R is theith component function of φ
,
i
=
1
,
…
,
d.Obviously, the component functions ofφ can be regarded as the functions defined on the manifold M and can be locally pulled back to the d-dimensional Euclidean space R
d (see Figure 4). According to (6), deduced in Section 3.2, the component functions can be Taylor-expanded in the neighbourhood X
x of x: for all x
′
∈
X
x,(7)
φ
i
x
′
=
φ
i
φ
x
-
1
∘
φ
x
x
′
=
φ
i
∘
φ
x
-
1
φ
x
x
′
=
φ
x
i
φ
x
x
′
=
φ
i
x
+
∇
φ
x
i
0
T
φ
x
x
′
+
1
2
φ
x
x
′
T
H
φ
x
i
0
φ
x
x
′
,where φ
x
i
=
φ
i
∘
φ
x
-
1 is the local pullback function of φ
i from X
x into Θ
x, i
=
1
,
…
,
d. Equation (7) can be rewritten into a matrix form:(8)
y
′
=
φ
x
′
=
φ
1
x
′
⋮
φ
d
x
′
=
φ
x
1
φ
x
x
′
⋮
φ
x
d
φ
x
x
′
=
φ
x
1
θ
′
⋮
φ
x
d
θ
′
=
φ
1
x
⋮
φ
d
x
+
∇
φ
x
1
0
T
⋮
∇
φ
x
d
0
T
φ
x
x
′
+
1
2
φ
x
x
′
T
H
φ
x
1
0
φ
x
x
′
⋮
φ
x
x
′
T
H
φ
x
d
0
φ
x
x
′
+
⋯
=
φ
x
+
A
x
φ
x
x
′
+
1
2
φ
x
x
′
T
H
φ
x
1
0
φ
x
x
′
⋮
φ
x
x
′
T
H
φ
x
d
0
φ
x
x
′
+
⋯
=
y
+
A
x
θ
′
+
1
2
θ
′
T
H
φ
x
1
0
θ
′
⋮
θ
′
T
H
φ
x
d
0
θ
′
+
⋯
,where A
x
=
∇
φ
x
1
0
T
⋮
∇
φ
x
d
0
T
∈
R
d
×
d. In (8), y
′
=
φ
x
′ is the global coordinate of x
′, while θ
′
=
φ
x
x
′ is the local coordinate of x
′. Equation (8) establishes the local relationship between y
′ and θ
′. Generally speaking, this relationship is nonlinear.Figure 4
The Local Pullback of component functions of global mapping;φ
i is the ith component function of φ and φ
i
∘
φ
x
-
1 is the pullback function of φ
i defined on Θ
x. Generally speaking, φ is nonlinear, so is φ
i
∘
φ
x
-
1
. If φ
i
∘
φ
x
-
1 is differentiable, then φ
i
∘
φ
x
-
1 can be Taylor-expanded in Θ
x.


## 5. The Local Linear Iterative Solution to Nonlinear Alignment

In algorithm, a matrixX
=
x
1
⋯
x
N
∈
R
D
×
N is given, where the column vectors of X are assumed to be taken from a d-dimensional, compact, and C
∞ differential manifold M
⊆
R
D which is embedded into the D-dimensional Euclidean space R
D, where d
≪
D; the manifold learning algorithms want to find a matrix Y
=
y
1
⋯
y
N
∈
R
d
×
N such that y
i
=
φ
x
i is the global coordinate of x
i, i
=
1
,
…
,
N. Under such circumstances, we construct our algorithm of local linear iterative alignment.


### 5.1. Linearization of Nonlinear Alignment

We first locally linearize the nonlinear relation of alignment deduced in Section4. For each data point x
n, let X
n
=
x
n
1
⋯
x
n
K
=
X
S
n be the neighbourhood of x
n, where S
n
∈
R
N
×
K is the selection matrix in which the n
k
t
h element of the kth column is 1; other elements are 0, k
=
1
,
…
,
K. It is noted that the neighbourhood X
n includes x
n itself. Let x
-
n
=
1
/
K
∑
k
=
1
K
x
n
k be the centre of X
n. From now on, X
n is regarded as the neighbourhood of x
-
n, no longer the neighbourhood of x
n.LetY
n
=
y
n
1
⋯
y
n
K
=
Y
S
n be the global coordinate of X
n, that is, y
n
k
=
φ
x
n
k, where k
=
1
,
…
,
K, and Θ
n
=
θ
n
,
1
⋯
θ
n
,
K the local coordinate of X
n, that is, θ
n
,
k
=
φ
n
x
n
k, where k
=
1
,
…
,
K and φ
n is the local homeomorphic mapping between X
n and Θ
n. According to (8) derived in Section 4, one has(9)
y
n
k
=
φ
x
n
k
=
φ
x
-
n
+
∇
φ
n
1
0
T
⋮
∇
φ
n
d
0
T
φ
n
x
n
k
+
1
2
φ
n
x
n
k
T
H
φ
n
1
0
φ
n
x
n
k
⋮
φ
n
x
n
k
T
H
φ
n
d
0
φ
n
x
n
k
+
⋯
=
φ
x
-
n
+
A
n
θ
n
,
k
+
1
2
θ
n
,
k
T
H
φ
n
1
0
θ
n
,
k
⋮
θ
n
,
k
T
H
φ
n
d
0
θ
n
,
k
+
⋯
,
k
=
1
,
…
,
K
,where φ
n
i
=
φ
i
∘
φ
n
-
1 is the local pullback function of φ
i from X
n to Θ
n, i
=
1
,
…
,
d.Equation (9) is a nonlinear equation. From the perspective of computational mathematics, a nonlinear equation can be solved by linear iteration. Therefore (9) has to be first linearized:(10)
y
n
k
≈
y
-
n
+
A
n
θ
n
,
k
,
k
=
1
,
…
,
K
,where y
-
n
=
1
/
K
∑
k
=
1
K
y
n
k is the linear part of φ
x
-
n. The error incurred from the linearization will be reduced again and again during the linear iteration.Equation (10) can be rewritten in matrix form:(11)
Y
^
n
=
y
n
1
⋯
y
n
K
-
y
-
n
⋯
y
-
n
=
Y
n
C
K
≈
A
n
θ
n
,
1
⋯
A
n
θ
n
,
K
=
A
n
θ
n
,
1
⋯
θ
n
,
K
=
A
n
Θ
n
,where C
K
=
I
K
-
1
/
K
Γ
K
Γ
K
T is the centralizing matrix, Γ
K
=
1
⋯
1
T
∈
R
K. In geometry, (11) means that Y
n, the global coordinate of the patch X
n, can be locally approximated by translation, rotation, and scaling of Θ
n, the local coordinate of the patch X
n.


### 5.2. Local Linear Iterative Alignment (LLIA) Algorithm

In the proposed LLIA algorithm, the global coordinateY is approximated iteratively:(12)
Y
0
⟶
Y
1
⟶
⋯
⟶
Y
p
⟶
Y
p
+
1
⟶
⋯
⟶
Y
.In the above iteration the initial iterative value Y
0 is locally set to be the local coordinates Y
n
0
=
Θ
n, while the other iterative values Y
p
+
1 are derived from the last iterative values Y
p based on the following local linear relation of alignment:(13)
Y
^
n
p
+
1
=
A
n
p
Y
^
n
p
,
p
=
0,1
,
2
,
…
,where Y
^
n
p
=
Y
p
S
n
C
K, Y
^
n
p
+
1
=
Y
p
+
1
S
n
C
K. The deduction of Y
n
p
+
1 from Y
p is as follows:(14)
∑
n
=
1
N
Y
^
n
p
+
1
-
A
n
p
Y
^
n
p
2
=
∑
n
=
1
N
Y
^
n
p
+
1
I
K
-
Y
^
n
p
+
Y
^
n
p
2
=
∑
n
=
1
N
Y
p
+
1
S
n
C
K
I
K
-
Y
^
n
p
+
Y
^
n
p
2
=
∑
n
=
1
N
Y
p
+
1
L
n
p
2
=
∑
n
=
1
N
tr
⁡
Y
p
+
1
L
n
p
L
n
p
T
Y
p
+
1
T
=
tr
⁡
Y
p
+
1
∑
n
=
1
N
L
n
p
L
n
p
T
Y
p
+
1
T
=
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
=
Y
p
+
1
Y
p
+
1
T
=
I
d
m
i
n
,where Y
^
n
p
+ is the solution to the following problem:(15)
I
d
-
Y
^
n
p
Y
^
n
p
+
2
=
Y
^
n
p
+
m
i
n
.The algorithm framework of iterative alignment is as follows.The Beginning of Iterationp
=
0
CalculateY
^
n
p:(16)
Y
^
n
p
=
Θ
n
p
=
0
Y
p
S
n
C
K
p
≥
1
,
n
=
1
,
…
,
N
CalculateY
^
n
p
+: (17)
I
d
-
Y
^
n
p
Y
^
n
p
+
2
=
Y
^
n
p
+
m
i
n
,
n
=
1
,
…
,
N
CalculateL
n
p:(18)
L
n
p
=
S
n
C
K
I
K
-
Y
^
n
p
+
Y
^
n
p
,
n
=
1
,
…
,
N
CalculateL
p: (19)
L
p
=
∑
n
=
1
N
L
n
p
L
n
p
T
CalculateY
p
+
1: (20)
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
=
Y
p
+
1
Y
p
+
1
T
=
I
d
m
i
n
Calculateε
p
+
1: (21)
ε
p
+
1
=
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
Ifε
p
+
1
>
ε, then p
=
p
+
1 and go back to calculate Y
^
n
pThe End of Iteration.


## 5.1. Linearization of Nonlinear Alignment

We first locally linearize the nonlinear relation of alignment deduced in Section4. For each data point x
n, let X
n
=
x
n
1
⋯
x
n
K
=
X
S
n be the neighbourhood of x
n, where S
n
∈
R
N
×
K is the selection matrix in which the n
k
t
h element of the kth column is 1; other elements are 0, k
=
1
,
…
,
K. It is noted that the neighbourhood X
n includes x
n itself. Let x
-
n
=
1
/
K
∑
k
=
1
K
x
n
k be the centre of X
n. From now on, X
n is regarded as the neighbourhood of x
-
n, no longer the neighbourhood of x
n.LetY
n
=
y
n
1
⋯
y
n
K
=
Y
S
n be the global coordinate of X
n, that is, y
n
k
=
φ
x
n
k, where k
=
1
,
…
,
K, and Θ
n
=
θ
n
,
1
⋯
θ
n
,
K the local coordinate of X
n, that is, θ
n
,
k
=
φ
n
x
n
k, where k
=
1
,
…
,
K and φ
n is the local homeomorphic mapping between X
n and Θ
n. According to (8) derived in Section 4, one has(9)
y
n
k
=
φ
x
n
k
=
φ
x
-
n
+
∇
φ
n
1
0
T
⋮
∇
φ
n
d
0
T
φ
n
x
n
k
+
1
2
φ
n
x
n
k
T
H
φ
n
1
0
φ
n
x
n
k
⋮
φ
n
x
n
k
T
H
φ
n
d
0
φ
n
x
n
k
+
⋯
=
φ
x
-
n
+
A
n
θ
n
,
k
+
1
2
θ
n
,
k
T
H
φ
n
1
0
θ
n
,
k
⋮
θ
n
,
k
T
H
φ
n
d
0
θ
n
,
k
+
⋯
,
k
=
1
,
…
,
K
,where φ
n
i
=
φ
i
∘
φ
n
-
1 is the local pullback function of φ
i from X
n to Θ
n, i
=
1
,
…
,
d.Equation (9) is a nonlinear equation. From the perspective of computational mathematics, a nonlinear equation can be solved by linear iteration. Therefore (9) has to be first linearized:(10)
y
n
k
≈
y
-
n
+
A
n
θ
n
,
k
,
k
=
1
,
…
,
K
,where y
-
n
=
1
/
K
∑
k
=
1
K
y
n
k is the linear part of φ
x
-
n. The error incurred from the linearization will be reduced again and again during the linear iteration.Equation (10) can be rewritten in matrix form:(11)
Y
^
n
=
y
n
1
⋯
y
n
K
-
y
-
n
⋯
y
-
n
=
Y
n
C
K
≈
A
n
θ
n
,
1
⋯
A
n
θ
n
,
K
=
A
n
θ
n
,
1
⋯
θ
n
,
K
=
A
n
Θ
n
,where C
K
=
I
K
-
1
/
K
Γ
K
Γ
K
T is the centralizing matrix, Γ
K
=
1
⋯
1
T
∈
R
K. In geometry, (11) means that Y
n, the global coordinate of the patch X
n, can be locally approximated by translation, rotation, and scaling of Θ
n, the local coordinate of the patch X
n.


## 5.2. Local Linear Iterative Alignment (LLIA) Algorithm

In the proposed LLIA algorithm, the global coordinateY is approximated iteratively:(12)
Y
0
⟶
Y
1
⟶
⋯
⟶
Y
p
⟶
Y
p
+
1
⟶
⋯
⟶
Y
.In the above iteration the initial iterative value Y
0 is locally set to be the local coordinates Y
n
0
=
Θ
n, while the other iterative values Y
p
+
1 are derived from the last iterative values Y
p based on the following local linear relation of alignment:(13)
Y
^
n
p
+
1
=
A
n
p
Y
^
n
p
,
p
=
0,1
,
2
,
…
,where Y
^
n
p
=
Y
p
S
n
C
K, Y
^
n
p
+
1
=
Y
p
+
1
S
n
C
K. The deduction of Y
n
p
+
1 from Y
p is as follows:(14)
∑
n
=
1
N
Y
^
n
p
+
1
-
A
n
p
Y
^
n
p
2
=
∑
n
=
1
N
Y
^
n
p
+
1
I
K
-
Y
^
n
p
+
Y
^
n
p
2
=
∑
n
=
1
N
Y
p
+
1
S
n
C
K
I
K
-
Y
^
n
p
+
Y
^
n
p
2
=
∑
n
=
1
N
Y
p
+
1
L
n
p
2
=
∑
n
=
1
N
tr
⁡
Y
p
+
1
L
n
p
L
n
p
T
Y
p
+
1
T
=
tr
⁡
Y
p
+
1
∑
n
=
1
N
L
n
p
L
n
p
T
Y
p
+
1
T
=
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
=
Y
p
+
1
Y
p
+
1
T
=
I
d
m
i
n
,where Y
^
n
p
+ is the solution to the following problem:(15)
I
d
-
Y
^
n
p
Y
^
n
p
+
2
=
Y
^
n
p
+
m
i
n
.The algorithm framework of iterative alignment is as follows.The Beginning of Iterationp
=
0
CalculateY
^
n
p:(16)
Y
^
n
p
=
Θ
n
p
=
0
Y
p
S
n
C
K
p
≥
1
,
n
=
1
,
…
,
N
CalculateY
^
n
p
+: (17)
I
d
-
Y
^
n
p
Y
^
n
p
+
2
=
Y
^
n
p
+
m
i
n
,
n
=
1
,
…
,
N
CalculateL
n
p:(18)
L
n
p
=
S
n
C
K
I
K
-
Y
^
n
p
+
Y
^
n
p
,
n
=
1
,
…
,
N
CalculateL
p: (19)
L
p
=
∑
n
=
1
N
L
n
p
L
n
p
T
CalculateY
p
+
1: (20)
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
=
Y
p
+
1
Y
p
+
1
T
=
I
d
m
i
n
Calculateε
p
+
1: (21)
ε
p
+
1
=
tr
⁡
Y
p
+
1
L
p
Y
p
+
1
T
Ifε
p
+
1
>
ε, then p
=
p
+
1 and go back to calculate Y
^
n
pThe End of Iteration.


## 6. Experimental Results

Here the experimental results of 8 manifold learning algorithms on the toy and real-world data are presented. The 8 manifold learning algorithms are the proposed local linear iterative alignment (LLIA) algorithm, LLE, HLLE, LTSA, Diffusion Map, MVU, ISOMAP, and LE. The last 7 manifold learning algorithms are implemented by using MANI, a widely used platform of manifold learning which can be downloaded from internet [30].


### 6.1. Toy Data

The toy data used in the experiments are Trefoil, Punctured Sphere, and Toroidal Helix. These toy data are also produced by using MANI. Figures5, 6, and 7 show the experimental results of 8 manifold learning algorithms on three toy datasets. At present there are no widely accepted quantitative evaluation criteria in manifold learning [31]. The evaluations of manifold learning algorithms are commonly based on visual perception.Figure 5
The experimental results on Trefoil.Figure 6
The experimental results on Punctured Sphere.Figure 7
The experimental results on Toroidal Helix.At the top of Figure5, an image of Trefoil and some coloured data taken from Trefoil are presented. Since Trefoil is constructed by twisting a planar coil into a cubic body, a good manifold learning algorithm should be able to recover the planar coil from the given coloured data and keep the order of colours unchanged. It can be seen from Figure 5 that the proposed LLIA algorithm does a good job in this respect.The so-called Punctured Sphere is a spherical surface whose top has been cut off. The colour of the given data shown in Figure6 indicates the position relationship between the given data. The aim of manifold learning is to produce an overhead view of Punctured Sphere on a plane. It can be seen from Figure 6 that the proposed algorithm achieves much better results than other manifold learning algorithms.Toroidal Helix is something like that shown at the top of Figure7. Although Toroidal Helix is much more complicated than Trefoil, it is also constructed by twisting a planar coil into a cubic body. The aim of manifold learning is also to recover the planar coil from the given coloured data. In doing so, the order of data colour must be kept unchanged because the order of data colour indicates the position relationship of data which should not be damaged during dimension reduction. It can be seen from Figure 7 that the performance of the proposed LLIA algorithm is one of the best among 8 manifold learning algorithms.Table1 shows the average alignment errors of the proposed LLIA algorithm during iterations. It can be seen from Table 1 that the initial alignment errors are considerably large and will be reduced sharply to almost zero during the first 2 iterations. The fact that the initial alignment errors are considerably large indirectly verifies the nonlinearity of alignment and justifies the necessity of iterative alignment. Furthermore the fact that the errors of iterative alignment will be reduced sharply to almost zero during the first 2 iterations means that the time complexity of the proposed LLIA algorithm is quite low.Table 1
Average alignment errors of LLIA algorithm on Trefoil, Punctured Sphere, and Toroidal Helix during iterations.
Iterative times
Average alignment errors (repeated 10 times)
Trefoil
Punctured Sphere
ToroidalHelix
1
2.430325527
6.1876
00
1.42672
0000
2
0.208952049
1.482
000
0.34336
0000
3
5.53147
E
-
05
0.00019
0
2.46957
E
-
06
4
5.56803
E
-
09
4.85
E
-
08
2.05993
E
-
11
5
1.37933
E
-
12
1.36
E
-
11
3.603
00
E
-
14
6
2.2728
E
-
14
3.77
E
-
14
3.50165
E
-
14
7
2.22939
E
-
14
3.59
E
-
14
3.40432
E
-
14
8
2.28014
E
-
14
3.56
E
-
14
3.50757
E
-
14
9
2.3272
E
-
14
3.53
E
-
14
3.47241
E
-
14
10
2.22417
E
-
14
3.51
E
-
14
3.47867
E
-
14


### 6.2. Real-World Data

Figure8 shows the experimental results of 8 manifold learning algorithms on the dataset of Frey Face. Frey Face is often used to test the effects of manifold learning algorithms in many academic literatures [1, 3, 32, 33]. The photos in Frey Face are all taken from the same person with different head poses and facial expressions. Therefore, although the dimension of photos is 560, the intrinsic dimension of photos is two: head pose and facial expression. In Figure 8, the photos are dimensionally reduced from 560 to 2 by using 8 different manifold learning algorithms, including the proposed LLIA algorithm. In the images of Figure 8, the facial expression changes along the vertical direction, while the head pose changes along the horizontal direction. It can be seen that the proposed LLIA algorithm achieves the best visual effect among the 8 manifold learning algorithms.Figure 8
The experimental results on Frey Face.Figure9 shows the experimental results on the dataset of plaster. Plaster is also a dataset often used to test the effects of manifold learning algorithms in many academic literatures [2, 33]. The photos of plaster are all taken from the same plaster from different shooting angle and under different shooting illumination. Therefore, although the dimension of photos is 4096
=
20
×
28, the intrinsic dimension of photos is two: shooting angle and illumination. In Figure 9, the photos are dimensionally reduced from 4096 to 2 by using manifold learning algorithms. In the images of Figure 9, the shooting angle changes along the vertical direction, while the shooting illumination changes along the horizontal direction. Again, it can be seen that the proposed LLIA algorithm achieves the best visual effect among the 8 manifold learning algorithms.Figure 9
The experimental results on plaster.As shown in Figures5, 6, 7, 8, and 9, the effects of manifold learning algorithms are evaluated qualitatively, not quantitatively. At present, there are no widely accepted quantitative evaluation criteria in manifold learning [31]. However, the evaluations of manifold learning algorithms can be quantized indirectly by applying manifold learning algorithms to practical applications. In Table 2, the manifold learning algorithms are applied to the clustering application. USPS is an image dataset of handwritten numerals and has been used in many academic literatures of manifold learning [3, 34]. In Table 2, the images are first dimensionally reduced by using manifold learning algorithms and then clustered by using theK-means algorithm. The clustering precisions shown in Table 2 are then used to evaluate the effects of manifold learning algorithms indirectly. It can be seen from Figure 11 that the proposed LLIA algorithm is superior to LLE, HLLE, LTSA, and Diffusion Map but inferior to ISOMAP and LE. Note that both ISOMAP and LE belong to the so-called global preserving algorithms, while the proposed LLIA, LLE, HLLE, LTSA, and Diffusion Map belong to the so-called local preserving algorithms. Table 2 shows that, in the clustering of handwritten numerals, although the local preserving algorithms are inferior to the global preserving algorithms, the proposed LLIA achieves the best result among the local preserving algorithms.Table 2
Clustering accuracy of USPS by using the 2D embedding.
2 clusters
3 clusters
4 clusters
Average
ISOMAP
0.948000000
0.792888889
0.665888889
0.802259259
LE
0.793222222
0.705666667
0.641000000
0.713296296
LLIA
0.934333333
0.693111111
0.493333333
0.706925926
LTSA
0.879888889
0.643000000
0.505222222
0.676037037
LLE
0.821222222
0.666888889
0.508000000
0.66537037
HLLE
0.587888889
0.396777778
0.293222222
0.425962963
Diff. map
0.501333333
0.336333333
0.254111111
0.363925926


### 6.3. Robustness Experiments

Figures10 and 11 show the robustness experiments against the change of neighbourhood size on Toroidal Helix and Punctured Sphere. The experimental data as well as the experimental results of manifold learning algorithms (except LLIA) are provided by using the manifold learning platform MANI.Figure 10
The robustness experiments against the change of neighbourhood sizes on Toroidal Helix.Figure 11
The robustness experiments against the change of neighbourhood sizes on Punctured Sphere.It can be seen in Figure10 that, on Toroidal Helix, the proposed algorithm LLIA performs best among the listed manifold learning algorithms. The experimental results of other manifold learning algorithms deform very much along with the change ofK. However, as shown in Figure 11, most of the listed manifold learning algorithms (including LLIA) perform stably on Punctured Sphere. Anyway, the proposed LLIA algorithm shows some robustness against the different neighbourhood sizes as well as the different manifolds.Figures12 and 13 show the robustness experiments against noises on Toroidal Helix and Punctured Sphere. The noises are added by using the manifold learning platform MANI. There are two Matlab sentences in MANI which can be used to add noises to the manifold data:noiseSigma = handles.noise;
handles.X = handles.X + noiseSigma∗ randn(N,3).In the above Matlab sentences, the variable noiseSigma controls the noise strength. In Figures 12 and 13, the noise strength has been changed from 0 to 18%.Figure 12
The robustness experiments against noises on Toroidal Helix.Figure 13
The robustness experiments against noises on Punctured Sphere.It can be seen in Figure12 that, on Toroidal Helix, the performance of proposed algorithm LLIA is quite robust against noises, while other manifold learning algorithms deteriorate quickly when the noises are strengthened steadily. On the other hand, on Punctured Sphere, ISOMAP, Diffusion Map, and the proposed LLIA perform stably against the change of noises. Anyway, it can be concluded from both Figure 12 and Figure 13 that the proposed LLIA algorithm is robust against noises on different manifolds and different noise strength.


## 6.1. Toy Data

The toy data used in the experiments are Trefoil, Punctured Sphere, and Toroidal Helix. These toy data are also produced by using MANI. Figures5, 6, and 7 show the experimental results of 8 manifold learning algorithms on three toy datasets. At present there are no widely accepted quantitative evaluation criteria in manifold learning [31]. The evaluations of manifold learning algorithms are commonly based on visual perception.Figure 5
The experimental results on Trefoil.Figure 6
The experimental results on Punctured Sphere.Figure 7
The experimental results on Toroidal Helix.At the top of Figure5, an image of Trefoil and some coloured data taken from Trefoil are presented. Since Trefoil is constructed by twisting a planar coil into a cubic body, a good manifold learning algorithm should be able to recover the planar coil from the given coloured data and keep the order of colours unchanged. It can be seen from Figure 5 that the proposed LLIA algorithm does a good job in this respect.The so-called Punctured Sphere is a spherical surface whose top has been cut off. The colour of the given data shown in Figure6 indicates the position relationship between the given data. The aim of manifold learning is to produce an overhead view of Punctured Sphere on a plane. It can be seen from Figure 6 that the proposed algorithm achieves much better results than other manifold learning algorithms.Toroidal Helix is something like that shown at the top of Figure7. Although Toroidal Helix is much more complicated than Trefoil, it is also constructed by twisting a planar coil into a cubic body. The aim of manifold learning is also to recover the planar coil from the given coloured data. In doing so, the order of data colour must be kept unchanged because the order of data colour indicates the position relationship of data which should not be damaged during dimension reduction. It can be seen from Figure 7 that the performance of the proposed LLIA algorithm is one of the best among 8 manifold learning algorithms.Table1 shows the average alignment errors of the proposed LLIA algorithm during iterations. It can be seen from Table 1 that the initial alignment errors are considerably large and will be reduced sharply to almost zero during the first 2 iterations. The fact that the initial alignment errors are considerably large indirectly verifies the nonlinearity of alignment and justifies the necessity of iterative alignment. Furthermore the fact that the errors of iterative alignment will be reduced sharply to almost zero during the first 2 iterations means that the time complexity of the proposed LLIA algorithm is quite low.Table 1
Average alignment errors of LLIA algorithm on Trefoil, Punctured Sphere, and Toroidal Helix during iterations.
Iterative times
Average alignment errors (repeated 10 times)
Trefoil
Punctured Sphere
ToroidalHelix
1
2.430325527
6.1876
00
1.42672
0000
2
0.208952049
1.482
000
0.34336
0000
3
5.53147
E
-
05
0.00019
0
2.46957
E
-
06
4
5.56803
E
-
09
4.85
E
-
08
2.05993
E
-
11
5
1.37933
E
-
12
1.36
E
-
11
3.603
00
E
-
14
6
2.2728
E
-
14
3.77
E
-
14
3.50165
E
-
14
7
2.22939
E
-
14
3.59
E
-
14
3.40432
E
-
14
8
2.28014
E
-
14
3.56
E
-
14
3.50757
E
-
14
9
2.3272
E
-
14
3.53
E
-
14
3.47241
E
-
14
10
2.22417
E
-
14
3.51
E
-
14
3.47867
E
-
14


## 6.2. Real-World Data

Figure8 shows the experimental results of 8 manifold learning algorithms on the dataset of Frey Face. Frey Face is often used to test the effects of manifold learning algorithms in many academic literatures [1, 3, 32, 33]. The photos in Frey Face are all taken from the same person with different head poses and facial expressions. Therefore, although the dimension of photos is 560, the intrinsic dimension of photos is two: head pose and facial expression. In Figure 8, the photos are dimensionally reduced from 560 to 2 by using 8 different manifold learning algorithms, including the proposed LLIA algorithm. In the images of Figure 8, the facial expression changes along the vertical direction, while the head pose changes along the horizontal direction. It can be seen that the proposed LLIA algorithm achieves the best visual effect among the 8 manifold learning algorithms.Figure 8
The experimental results on Frey Face.Figure9 shows the experimental results on the dataset of plaster. Plaster is also a dataset often used to test the effects of manifold learning algorithms in many academic literatures [2, 33]. The photos of plaster are all taken from the same plaster from different shooting angle and under different shooting illumination. Therefore, although the dimension of photos is 4096
=
20
×
28, the intrinsic dimension of photos is two: shooting angle and illumination. In Figure 9, the photos are dimensionally reduced from 4096 to 2 by using manifold learning algorithms. In the images of Figure 9, the shooting angle changes along the vertical direction, while the shooting illumination changes along the horizontal direction. Again, it can be seen that the proposed LLIA algorithm achieves the best visual effect among the 8 manifold learning algorithms.Figure 9
The experimental results on plaster.As shown in Figures5, 6, 7, 8, and 9, the effects of manifold learning algorithms are evaluated qualitatively, not quantitatively. At present, there are no widely accepted quantitative evaluation criteria in manifold learning [31]. However, the evaluations of manifold learning algorithms can be quantized indirectly by applying manifold learning algorithms to practical applications. In Table 2, the manifold learning algorithms are applied to the clustering application. USPS is an image dataset of handwritten numerals and has been used in many academic literatures of manifold learning [3, 34]. In Table 2, the images are first dimensionally reduced by using manifold learning algorithms and then clustered by using theK-means algorithm. The clustering precisions shown in Table 2 are then used to evaluate the effects of manifold learning algorithms indirectly. It can be seen from Figure 11 that the proposed LLIA algorithm is superior to LLE, HLLE, LTSA, and Diffusion Map but inferior to ISOMAP and LE. Note that both ISOMAP and LE belong to the so-called global preserving algorithms, while the proposed LLIA, LLE, HLLE, LTSA, and Diffusion Map belong to the so-called local preserving algorithms. Table 2 shows that, in the clustering of handwritten numerals, although the local preserving algorithms are inferior to the global preserving algorithms, the proposed LLIA achieves the best result among the local preserving algorithms.Table 2
Clustering accuracy of USPS by using the 2D embedding.
2 clusters
3 clusters
4 clusters
Average
ISOMAP
0.948000000
0.792888889
0.665888889
0.802259259
LE
0.793222222
0.705666667
0.641000000
0.713296296
LLIA
0.934333333
0.693111111
0.493333333
0.706925926
LTSA
0.879888889
0.643000000
0.505222222
0.676037037
LLE
0.821222222
0.666888889
0.508000000
0.66537037
HLLE
0.587888889
0.396777778
0.293222222
0.425962963
Diff. map
0.501333333
0.336333333
0.254111111
0.363925926


## 6.3. Robustness Experiments

Figures10 and 11 show the robustness experiments against the change of neighbourhood size on Toroidal Helix and Punctured Sphere. The experimental data as well as the experimental results of manifold learning algorithms (except LLIA) are provided by using the manifold learning platform MANI.Figure 10
The robustness experiments against the change of neighbourhood sizes on Toroidal Helix.Figure 11
The robustness experiments against the change of neighbourhood sizes on Punctured Sphere.It can be seen in Figure10 that, on Toroidal Helix, the proposed algorithm LLIA performs best among the listed manifold learning algorithms. The experimental results of other manifold learning algorithms deform very much along with the change ofK. However, as shown in Figure 11, most of the listed manifold learning algorithms (including LLIA) perform stably on Punctured Sphere. Anyway, the proposed LLIA algorithm shows some robustness against the different neighbourhood sizes as well as the different manifolds.Figures12 and 13 show the robustness experiments against noises on Toroidal Helix and Punctured Sphere. The noises are added by using the manifold learning platform MANI. There are two Matlab sentences in MANI which can be used to add noises to the manifold data:noiseSigma = handles.noise;
handles.X = handles.X + noiseSigma∗ randn(N,3).In the above Matlab sentences, the variable noiseSigma controls the noise strength. In Figures 12 and 13, the noise strength has been changed from 0 to 18%.Figure 12
The robustness experiments against noises on Toroidal Helix.Figure 13
The robustness experiments against noises on Punctured Sphere.It can be seen in Figure12 that, on Toroidal Helix, the performance of proposed algorithm LLIA is quite robust against noises, while other manifold learning algorithms deteriorate quickly when the noises are strengthened steadily. On the other hand, on Punctured Sphere, ISOMAP, Diffusion Map, and the proposed LLIA perform stably against the change of noises. Anyway, it can be concluded from both Figure 12 and Figure 13 that the proposed LLIA algorithm is robust against noises on different manifolds and different noise strength.


## 7. Conclusions

(1)
At present, many machine learning algorithms, including the famous LLE algorithm [1, 35], claim to be manifold learning algorithms. However, the manifolds mentioned in these algorithms seem to have nothing to do with the manifolds defined in mathematics. In contrast, the LLIA algorithm proposed on this paper is constructed based on the mathematical characteristics (local homeomorphism, local pullback, etc.) of differential manifolds.
(2)
The manifold learning can be divided into two stages: local homeomorphism and alignment. In local homeomorphism, a Taylor expansion between a patch and its local coordinate can be deduced by using one-parameter transformation group acting on manifolds [5, 36]. In this paper, a Taylor expansion between the global and local coordinates of a patch is also deduced by using the local pullback of functions defined on differential manifold. It should be pointed out that these two Taylor expansions are completely different. The former reveals the relation between the high-dimensional data and low-dimensional date, while the latter reveals the relation between two low-dimensional data.
(3)
In the proposed LLIA algorithm, the nonlinear problem is solved by using a linear iteration method. There are two problems to be addressed here: the convergence of iteration and the time complexity of algorithm. In computational mathematics, the linear iterative methods are often used to solve nonlinear problems and the convergences of iteration have been thoroughly discussed [37]. In practice, the experimental results presented in this paper show that the alignment errors would be considerably large if without iteration and will be reduced sharply during the first two iterations. This fact also implies that the time complexity of the proposed LLIA algorithm will be quite low because only few iterations are needed.
(4)
At present, the algorithms of local coordinate alignment can be divided into two categories: the one-time alignment and the gradual alignment. In the one-time alignment, the manifold’s global coordinate is obtained at one time by solving an eigenvalue problem [3, 5, 12–14], while in the gradual alignment, the manifold’s global coordinate grows up gradually from a patch’s local coordinate [9–11]. No matter which alignment is used, they are all based on the local linear model of alignment. The proposed LLIA algorithm is based on the nonlinear model of alignment and therefore belongs to neither one-time alignment nor gradual alignment.



---

*Source: 7196043-2016-09-07.xml*