Lecture Notes in Computer Science

Local Coordinates Alignment and Its Linearization 

Tianhao Zhang

1,3

, Xuelong Li

2

, Dacheng Tao

3

, and Jie Yang

1 

1

 Institute of IP & PR, Shanghai Jiao Tong Univ., P.R. China 

2

 Sch. of Comp. Sci. and Info. Sys., Birkbeck, Univ. of London, U.K. 

3

 Dept. of Computing, Hong Kong Polytechnic Univ., Hong Kong 

{z.tianhao,dacheng.tao}@gmail.com, [e-mail],  

[e-mail] 

Abstract. Manifold learning has been demonstrated to be an effective way to 

discover the intrinsic geometrical structure of a number of samples. In this paper, 

a new manifold learning algorithm, Local Coordinates Alignment (LCA), is 

developed based on the alignment technique. LCA first obtains the local 

coordinates as representations of a local neighborhood by preserving the 

proximity relations on the patch which is Euclidean; and then the extracted local 

coordinates are aligned to yield the global embeddings. To solve the out of 

sample problem, the linearization of LCA (LLCA) is also proposed. Empirical 

studies on both synthetic data and face images show the effectiveness of LCA 

and LLCA in comparing with existing manifold learning algorithms and linear 

subspace methods. 

Keywords:  Manifold learning, Local Coordinates Alignment, dimensionality 

reduction. 

1   Introduction 

Manifold learning addresses the problem of discovering the intrinsic structure of the 

manifold from a number of samples. The generic problem of manifold learning can be 

described as following. Consider a dataset 

X

, which consists of N  samples 

i

x  

(

1

i

N

≤ ≤

) in a high dimensional Euclidean space 

m

. That is 

[

]

1

,

,

m N

N

X

x

x

×

=

∈

. 

The sample 

i

x  is obtained by embedding a sample 

i

z , which is drawn from 

d

M

 (a low 

dimensional nonlinear manifold) to 

m

 (a higher dimensional Euclidean space,  d

m

<

), 

i.e., 

:

d

m

M

ϕ

→

 and 

( )

i

i

x

z

ϕ

=

. A manifold learning algorithm aims to find the 

corresponding low-dimensional representation 

i

y  in a low dimensional Euclidean space 

d

 of 

i

x  to preserve the geometric property of 

d

M

. 

Recently, a number of manifold learning algorithms have been developed for pattern 

analysis, classification, clustering, and dimensionality reduction. Each algorithm detects 

a specific intrinsic, i.e., geometrical, structure of the underlying manifold of the raw 

data. The representative ones include ISOMAP [6], locally linear embedding (LLE) [7], 

Laplacian eigenmaps (LE) [1], local tangent space alignment (LTSA) [3], etc. 

644 

T. Zhang et al. 

ISOMAP is a variant of MDS [13]. Unlike MDS, the distance measure between two 

samples is not the Euclidean distance but the geodesic distance, which is the shortest 

path from one sample to another computed by the Dijkstra’s algorithm. ISOMAP is 

intrinsically a global approach since it attempts to preserve the global geodesic 

distances of all pairs of samples. Different from ISOMAP, LLE, LE and LTSA are all 

local methods, which preserve the geometrical structure of every local neighborhood. 

LLE uses the linear coefficients, which reconstruct the given point by its neighbors, to 

represent the local structure, and then seeks a low-dimensional embedding, in which 

these coefficients are still suitable for reconstructions. LE is developed based on the 

Laplace Beltrami operator in the spectral graph theory [1,4]. This operator provides an 

optimal embedding for a manifold. The algorithm preserves proximity relationships by 

the manipulations on the undirected weighted graph, which indicates the neighbor 

relations of the pairwise points. LTSA exploits the local tangent information as a 

representation of the local structure and this local information is then aligned to give the 

global coordinates. 

Inspired by LTSA [3], we propose a new manifold learning algorithm, i.e., Local 

Coordinates Alignment (LCA). LCA obtains the local coordinates as representations of 

a local neighborhood by preserving the proximity relations on the patch. The extracted 

local coordinates are then aligned by the alignment trick [3] to yield the global 

embeddings. In LCA, the local representation and the global alignment are explicitly 

implemented as two steps for intrinsic structure discovery. In addition, to solve the out 

of sample problem, the linear approximation is applied to LCA, called Linear LCA or 

LLCA. Experimental results show that LCA discovers the manifold structure, and 

LLCA outperforms representative subspace methods for the face recognition.  

The rest of the paper is organized as follows: Section 2 describes LCA and its 

linearization is given in Section 3. Section 4 shows the empirical studies over synthetic 

data and face databases. Section 5 concludes. 

2   LCA: Local Coordinates Alignment 

The proposed algorithm is based on the assumption that each local neighborhood of the 

manifold 

d

M

 is intrinsically Euclidean, i.e., it is homeomorphic to an open subset of 

the Euclidean space with dimension  d . The proposed LCA extracts local coordinates 

by preserving the neighbor relationships of the raw data, and then obtains the optimal 

embeddings by aligning these local coordinates in globality. 

2.1   Local Representations 

Given an arbitrary sample 

m

i

x

∈

 and its  k  nearest neighbors 

1

,

,

k

i

i

x

x

, measured 

in terms of Euclidean distance, we let 

(

)

0

1

1

[

,

,

,

]

k

m

k

i

i

i

i

X

x

x

x

× +

=

∈

 denote  a 

neighborhood in the manifold 

d

M

, where 

0

i

i

x

x

=

. For 

i

X , we have the local map 

:

m

d

i

ψ

→

, i.e., 

(

)

0

1

1

:

[

,

,

,

]

k

d

k

i

i

i

i

i

i

X

Y

y

y

y

ψ

× +

=

∈

. Here, 

i

Y  is the local 

coordinates to parameterize the corresponding points in 

i

X . To yield the faithful maps, 

 

Local Coordinates Alignment and Its Linearization 

645 

we expect that the nearby points remain nearby, that is, the point 

0

d

i

y

∈

 is close to 

1

,

,

k

i

i

y

y

, i.e., 

0

0

2

1

arg min

j

i

k

i

i

y

j

y

y

=

−

∑

. 

(1) 

To capture the geometrical structure of the neighborhood, the weighting vector 

k

i

w

∈

 is introduce to (1) as 

( )

0

0

2

1

arg min

j

i

k

i

i

i

j

y

j

y

y

w

=

−

∑

, 

(2) 

where the j

th

 element of 

i

w

 is obtained by the heat kernel [4] with parameter  t

∈

, i.e., 

( )

0

2

exp

/

j

i

i

i

j

w

x

x

t

⎛

⎞

=

−

−

⎜

⎟

⎝

⎠

. 

(3) 

Vector 

i

w

 is a natural measure of distances between 

0

i

x

 and its neighbors. The 

larger the value 

( )

i

j

w

 is (the closer the point 

0

i

x

 is to the j

th

 neighbor), the more 

important is the corresponding neighbor. In setting 

t

= ∞

, Eq. (2) reduces to Eq. (1).  

To make further deduction, Eq. (2) is transformed to 

(

)

(

)

( )

0

1

0

1

0

0

0

arg min tr

,

,

diag

k

i

k

T

i

i

i

i

i

i

i

y

T

i

i

y

y

y

y

y

y

w

y

y

⎛

⎞

⎡

⎤

−

⎜

⎟

⎢

⎥

⎜

⎟

⎢

⎥ ⎡

⎤

−

−

⎣

⎦

⎜

⎟

⎢

⎥

⎜

⎟

⎢

⎥

⎜

⎟

−

⎣

⎦

⎝

⎠

, 

(4) 

where 

( )

tr

⋅

 denotes the trace operator, and 

( )

diag

⋅

 denotes the diagonal matrix whose 

diagonal entries are the corresponding components of the given vector. Let 

[

]

(

)

1

T

k

k

i

k

k

M

e

I

+ ×

= −

∈

, where 

[

]

1,

,1

T

k

k

e

=

∈

 and 

k

I

 is  the  k k

×

 identity 

matrix. Then, Eq. (4) reduces to: 

(

)

( )

(

)

( )

(

)

(

)

arg min tr

diag

arg min tr

diag

arg min tr

,

i

i

i

T

T

T

i

i

i

i

i

i

i

i

i

i

Y

Y

T

i

i i

Y

Y M

Y M

w

Y M

w M Y

Y L Y

=

=

 

(5) 

where 

( )

diag

T

i

i

i

i

L

M

w M

=

, which encapsulates the local geometric information. The 

matrix 

i

L

 is equivalent to: 

( )

[

]

( )

( )

1

diag

diag

k

T

i

i

k

j

j

i

i

k

k

k

i

i

w

w

e

L

w

e

I

I

w

w

=

⎡

⎤

−

−

⎡

⎤

⎢

⎥

=

−

=

⎢

⎥

⎢

⎥

⎣

⎦

⎢

⎥

−

⎣

⎦

∑

. 

(6) 

646 

T. Zhang et al. 

Therefore, according (5), the local coordinates 

i

Y  for  the  i

th

 neighborhood can be 

expressed. 

2.2   Global Alignment 

According to Section 2.1, local coordinates are obtained for all local neighborhoods 

respectively, namely 

1

2

,

,

,

N

Y Y

Y . In this section, these local coordinates are aligned to 

yield the global one. 

Let 

[

]

1

,

,

N

Y

y

y

=

 

denote the embedding coordinates which are faithful 

representations for 

[

]

1

,

,

N

X

x

x

=

 sampled from a manifold. Define the selection 

matrix 

( )

1

N

k

i

S

× +

∈

: 

( )

( )

1

0

i

q

i

pq

if p

h

S

else

⎧

=

⎪

=

⎨

⎪⎩

, 

(7) 

where, 

[

]

1

0

1

, ,

,

k

i

k

h

i i

i

+

=

∈

 

(8) 

denotes the set of indices for the i

th

 point and the corresponding neighbors. Then we can 

express the local coordinates 

i

Y  as the selective combinations of the embedding 

coordinates  Y  by using the selection matrix 

i

S : 

i

i

Y

YS

=

. 

(9) 

Now, we can write Eq. (5) as follows: 

(

)

arg min tr

T

T

i

i

i

Y

YS L S Y

. 

(10) 

For all samples, we have the global optimization: 

(

)

(

)

1

1

arg min

tr

arg min tr

arg min tr

N

N

T

T

T

T

i

i

i

i

i

i

Y

Y

i

i

T

Y

YS L S Y

Y

S L S Y

YLY

=

=

⎛

⎞

=

⎜

⎟

⎝

⎠

=

∑

∑

, 

(11) 

where 

1

N

T

i

i

i

i

L

S L S

=

=

∑

. The matrix L  can be termed by the alignment matrix [3] 

which is symmetric, positive semi-definite, and sparse. We can form the matrix  L  by 

the iterative procedure: 

( ) ( )

,

,

i

i

i

i

i

L h h

L h h

L

←

+

, 

(12) 

for 1 i

N

≤ ≤

 with the initialization 

0

L

=

. 

 

Local Coordinates Alignment and Its Linearization 

647 

To uniquely determine Y , we impose the constraint 

T

d

YY

I

=

，

where 

d

I  is  the 

d

d

×

 identity matrix. Now, the objective function is: 

(

)

arg min tr

      s.t.  

.

T

T

d

Y

YLY

YY

I

=

 

(13) 

The above minimization problem can be converted to solving an eigenvalue 

decomposition problem as follows: 

Lf

f

λ

=

. 

(14) 

The column vectors 

1

2

,

,

d

f f

f  in 

N

 are eigenvectors associated with ordered 

nonzero eigenvalues, 

1

2

d

λ λ

λ

<

< <

. Therefore, we obtain the embedding 

coordinates as: 

1

2

,

,

T

d

Y

f f

f

⎡

⎤

=

⎣

⎦ . 

(15) 

3   LLCA: Linear Local Coordinates Alignment 

LCA aims to detect the intrinsic features of nonlinear manifolds, but it fails in the out of 

sample problem. To solve this problem, the linearization approximation of LCA, i.e., 

Linear LCA (LLCA), is developed in this Section. LLCA finds the transformation 

matrix 

m d

A

×

∈

 that maps the dataset  X  to the dataset Y , i.e., 

T

Y

A X

=

. Thus, the 

linearized objective function (11) is: 

(

)

arg min tr

T

T

A

A XLX A . 

(16) 

Impose the column orthonormal constraint to  A , i.e. 

T

d

A A

I

=

, we have: 

(

)

arg min tr

       s.t.  

.

T

T

T

d

A

A XLX A

A A

I

=

 

(17) 

The solution of (17) is given by the eigenvalue decomposition: 

T

XLX

α λα

=

. 

(18) 

The transformation matrix  A  is 

[

]

1

2

,

,

d

A

α α

α

=

, 

(19) 

where 

1

2

,

,

d

α α

α

 are eigenvectors of 

T

XLX

 associated with the first 

d

 smallest 

eigenvalues. 

LLCA can be implemented in either an unsupervised or a supervised mode. In the 

later case, the label information is utilized, i.e., each neighborhood is replaced by points 

which have identical class label information. For a given point 

i

x  and its same-class 

648 

T. Zhang et al. 

points 

1

1

,

,

ni

i

i

x

x

−

, where ni  denotes the number of samples in this class, one can 

construct the vector 

1

ni

i

w

−

∈

 as follows: 

( )

0

2

exp

/

j

i

i

i

j

w

x

x

t

⎛

⎞

=

−

−

⎜

⎟

⎝

⎠

, 

1,

,

1

j

ni

=

−

. 

(20) 

Furthermore, to denote new indices set for the i

th

 point and its same-class points, one 

need reset 

[

]

0

1

1

, ,

,

ni

i

ni

h

i i

i

−

=

∈

. 

(21)