## Abstract

Spectral analysis‐based dimensionality reduction algorithms, especially the local manifold learning methods, have become popular recently because their optimizations do not involve local minima and scale well to large, high‐dimensional data sets. Despite their attractive properties, these algorithms are developed based on different geometric intuitions, and only partial information from the true geometric structure of the underlying manifold is learned by each method. In order to discover the underlying manifold structure more faithfully, we introduce a novel method to fuse the geometric information learned from different local manifold learning algorithms in this chapter. First, we employ local tangent coordinates to compute the local objects from different local algorithms. Then, we utilize the truncation function from differential manifold to connect the local objects with a global functional and finally develop an alternating optimization‐based algorithm to discover the low‐dimensional embedding. Experiments on synthetic as well as real data sets demonstrate the effectiveness of our proposed method.

### Keywords

- dimensionality reduction
- manifold learning

## 1. Introduction

Nonlinear dimensionality reduction (NLDR) plays an important role in the modern data analysis system, since many objects in our world can only be electronically represented with high‐dimensional data such as images, videos, speech signals, and text documents. We usually need to analyze a large amount of data and process them, and however, it is very complicated or even infeasible to process these high‐dimensional data directly, due to their high computational complexity on both time and space. Over the past decade, numerous manifold learning methods have been proposed for nonlinear dimensionality reduction. From methodology, these methods can be divided into two categories: global algorithms and local algorithms. Representative global algorithms contain isometric mapping [1], maximum variance unfolding [2], and local coordinates alignment with global preservation [3]. Local methods mainly include Laplacian eigenmaps (LEM) [4], locally linear embedding (LLE) [5], Hessian eigenmaps (HLLE) [6], local tangent space alignment (LTSA) [7], local linear transformation embedding [8], stable local approaches [9], and maximal linear embedding [10].

Different local approaches try to learn different geometric information of the underlying manifold, since they are developed based on the knowledge and experience of experts for their own purposes [11]. Therefore, only partial information from the true underlying manifold is learned by each existing local manifold learning method. Thus, to better discover the underlying manifold structure, it is more informative and essential to provide a common framework for synthesizing the geometric information extracted from different local methods. In this chapter, we propose an interesting method to unify the local manifold learning algorithms (e.g., LEM, LLE, HLLE, and LTSA). Inspired by HLLE which employs local tangent coordinates to compute the local Hessian, we propose to utilize local tangent coordinates to estimate the local objects defined in different local methods. Then, we employ the truncation function from differential manifold to connect the local objects with a global functional. Finally, we develop an alternating optimization‐based algorithm to discover the global coordinate system of lower dimensionality.

## 2. Local tangent coordinates system

A manifold is a topological space that locally resembles Euclidean space near every point. For example, around each point, there is a neighborhood that is topologically the same as the open unit ball in

A manifold can be represented by its coordinates. While the current research of differential geometry focuses on the characterization of the global properties of manifolds, NLDR algorithms, which try to find the coordinate representations of data, only need the local properties of manifolds. In this chapter, we use local coordinates associated with the tangent space to estimate the local objects over the manifold. To acquire the local tangent coordinates, we first perform Principal Component Analysis (PCA) [12] on the points in

An illustration of the local tangent space at

## 3. Reformulations of LEM, LLE, HLLE and LTSA using local tangent coordinates

### 3.1. Reformulation of Laplacian eigenmaps

The method LEM was introduced by Belkin and Niyogi [4]. We can summarize the geometrical motivation of LEM as follows. Assume that we are searching for a smooth one‐dimensional embedding

where

where the integral is taken with respect to the standard measure over the manifold. Thus, the function

Suppose that the tangent coordinate of

where

where

In order to compute the local object

Over

The least‐squares estimation of the operator

It is easy to show that the least‐squares solution of the above object function is

An unresolved problem in our reformulation is how to connect the local object

### 3.2. Reformulation of locally linear embedding

The LLE method was introduced by Roweis and Saul [5]. It is based on simple geometric intuitions, which can be depicted as follows. Globally, the data points are sampled from a nonlinear manifold, while each data point and its neighbors are residing on or close to a linear patch of the manifold locally. Thus, it is possible to describe the local geometric properties of the neighborhood of each data point in the high‐dimensional space by linear coefficients which reconstruct the data point from its neighbors under suitable conditions. The method of LLE computes the low‐dimensional embedding which is optimized to preserve the local configurations of the data. In each locally linear patch, the reconstruction error in the original LLE can be written as:

where

Since the geometric structure of the local patch can be approximated by its projection on the tangent space

where we have employed the fact that the weights sum to one, and

The optimal weights can be obtained analytically by minimizing the above reconstruction error. We solve the linear system of equations

and then normalize the solution by

where

where

### 3.3. Reformulation of Hessian eigenmaps

The HLLE method was introduced by Donoho and Grimes [6]. In contrast to LLE that obtains linear embedding by minimizing the

where

Here,

where

Over

Let

The least‐squares solution is

### 3.4. Reformulation of local tangent space alignment

The method LTSA was introduced by Zhang and Zha [7]. LTSA is based on similar geometric intuitions as LLE. The neighborhoods of each data point remain nearby and similarly colocated in the low‐dimensional space, if the data set is sampled from a smooth manifold. LLE constructs low‐dimensional data so that the local linear relations of the original data are preserved, while LTSA constructs a locally linear patch to approximate the tangent space at the point. The coordinates provided by the tangent space give a low‐dimensional representation of the patch. From Eq. (6), we can obtain:

From the above equation, we can discover that there are some relations between the global coordinate

where

where

Obviously, the optimal affine transformation

and therefore,

Let

## 4. Fusion of local manifold learning methods

So far we have discussed four basic local objects:

where

We employ the truncation function from differential manifold to connect the local objects with their corresponding global functional such that we can obtain a consistent alignment of the local objects to discover a single global coordinate system of lower dimensionality. The truncation function is a crucial tool in differential geometry to build relationships between global and local properties of the manifold. Assume that

The truncation function

where

where

where the power parameter

We propose to solve the objective function [Eq. (33)] by employing the alternating optimization [16] method, which iteratively updates

where

## 5. Experimental results

In this section, we experiment on both synthetic and real‐world data sets to evaluate the performance of our method, named FLM. For LEM, LLE, HLLE, LTSA, and our Fusion of local manifolds (FLM) algorithms, we experiment on these data sets to obtain both visualization and quantitative evaluations. We utilize the global smoothness and co‐directional consistence (GSCD) criteria [17] to quantitatively compare the embedding qualities of different algorithms: the smaller the value of GSCD, the higher the global smoothness, and the better the co‐directional consistence. There are two adjustable parameters in our FLM method, that is, the tuning parameter

### 5.1. Synthetic data sets

We first apply our FLM to the synthetic data sets that have been commonly used by other researchers: S‐Curve, Swiss Hole, Punctured Sphere, and Toroidal Helix. The character of these data sets can be summarized as: general, non‐convex, nonuniform, and noise, respectively. In each data set, we have total 1000 sample points, and the number of nearest neighbors is fixed to

On some particular data sets, the traditional local manifold learning methods perform well. For example, LEM works well on the Toroidal Helix; LLE works well on the Punctured Sphere; HLLE works well on the S‐Curve and Swiss Hole; and LTSA performs well on the S‐Curve, Swiss Hole, and Punctured Sphere.

In general, our FLM performs the best on all the four data sets.

The above consequence is because only partial geometric information of the underlying manifold is learned by each traditional local manifold learning method, while the complementary geometric information learned from different manifold learning algorithms is respected by our FLM method.

### 5.2. Real‐world data set

We next conduct experiments on the isometric feature mapping face (ISOFACE) data set [1], which contains 698 images of a 3‐D human head. The ISOFACE data set is collected under different poses and lighting directions. The resolution of each image is

As we can observe from Figure 6b and c, the embedding results of LEM and LLE show that the orientations of the faces change smoothly from left to right along the horizontal direction, and the orientations of the faces change from down to up along the vertical direction. However, as we can see at the right‐hand side of Figure 6b and c, the embedding results of both LEM and LLE come out to be severely compressed, and it is not obvious to survey the changes along the vertical direction.

As we can observe from Figure 6d and e, the horizontal rotation and variations in the brightness of the faces can be well revealed by the embedding result of HLLE and LTSA.

As we can observe from Figure 6f, orientations of the faces change smoothly from left to right along the horizontal direction, while the orientations of the faces change from down to up, and the light of the faces varies from bright to dark simultaneously along the vertical direction. These results illustrate that our FLM method successfully discovers the underlying manifold structure of the data set.

Our FLM performs the best on the ISOFACE data set, since our method makes full use of the complementary geometric information learned from different manifold learning methods. The corresponding GSCD results further verify the above visualization results in a quantitative way.

## 6. Conclusions

In this chapter, we introduce an interesting method, named FLM, which assumes a systematic framework to estimate the local objects and align them to reveal a single global low‐dimensional coordinate space. Within the framework, we can fuse together the geometric information learned from different local methods easily and effectively to better discover the underlying manifold structure. Experimental results on both the synthetic and real‐world data sets show that the proposed method leads to satisfactory results.

## Acknowledgments

This work was supported by the Fundamental Research Funds for the Central Universities of China, Natural Science Fund of Heilongjiang Province of China, and Natural Science Foundation of China under Grant No. HEUCF160415, F2015033, and 61573114.

## References

- 1.
Tenenbaum JB, De Silva V, Langford JC. A global geometric framework for nonlinear dimensionality reduction. Science. 2000;290(5500):2319–2323. - 2.
Weinberger KQ, Saul LK. Unsupervised learning of image manifolds by semidefinite programming. International Journal of Computer Vision. 2006;70(1):77–90. - 3.
Chen J, Ma Z, Liu Y. Local coordinates alignment with global preservation for dimensionality reduction. IEEE Transactions on Neural Networks and Learning Systems. 2013;24(1):106–117. - 4.
Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation. 2003;15(6):1373–1396. - 5.
Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science. 2000;290(5500):2323–2326. - 6.
Donoho DL, Grimes C. Hessian eigenmaps: locally linear embedding techniques for high‐dimensional data. Proceedings of the National Academy of Sciences. 2003;100(10):5591–5596. - 7.
Zhang ZY, Zha HY. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment. Journal of Shanghai University (English Edition). 2004;8(4):406–424. - 8.
Hou C, Wang J, Wu Y, Yi D. Local linear transformation embedding. Neurocomputing. 2009;72(10):2368–2378. - 9.
Hou C, Zhang C, Wu Y, Jiao Y. Stable local dimensionality reduction approaches. Pattern Recognition. 2009;42(9):2054–2066. - 10.
Wang R, Shan S, Chen X, Chen J, Gao W. Maximal linear embedding for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2011;33(9):1776–1792. - 11.
Yan S, Xu D, Zhang B, Zhang HJ, Yang Q, Lin S. Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2007;29(1):40–51. - 12.
Jolliffe I. Principal component analysis. Wiley Online Library; Springer-Verlag New York 2005. - 13.
Turk M, Pentland A. Eigenfaces for recognition. Journal of Cognitive Neuroscience. 1991;3(1):71–86. - 14.
Belkin M, Niyogi P. Towards a theoretical foundation for Laplacian‐based manifold methods. Journal of Computer and System Sciences. 2008;74(8):1289–1308. - 15.
Chern SS, Chen WH, Lam KS. Lectures on differential geometry. Vol. 1. World Scientific Pub Co Inc; Singapore 1999. - 16.
James C. Bezdek, Richard J. Hathaway. Some notes on alternating optimization. In: Advances in Soft Computing. Springer; Springer Berlin Heidelberg 2002. p. 288–300. - 17.
Zhang J, Wang Q, He L, Zhou ZH. Quantitative analysis of nonlinear embedding. IEEE Transactions on Neural Networks. 2011;22(12):1987–1998.