\documentclass{article}
\usepackage{fullpage}
\usepackage{parskip}
\usepackage{titlesec}
\usepackage{xcolor}
\usepackage[colorlinks = true,
linkcolor = blue,
urlcolor = blue,
citecolor = blue,
anchorcolor = blue]{hyperref}
\usepackage[natbibapa]{apacite}
\usepackage{eso-pic}
\AddToShipoutPictureBG{\AtPageLowerLeft{\includegraphics[scale=0.7]{powered-by-Authorea-watermark.png}}}
\renewenvironment{abstract}
{{\bfseries\noindent{\abstractname}\par\nobreak}\footnotesize}
{\bigskip}
\titlespacing{\section}{0pt}{*3}{*1}
\titlespacing{\subsection}{0pt}{*2}{*0.5}
\titlespacing{\subsubsection}{0pt}{*1.5}{0pt}
\usepackage{authblk}
\usepackage{graphicx}
\usepackage[space]{grffile}
\usepackage{latexsym}
\usepackage{textcomp}
\usepackage{longtable}
\usepackage{tabulary}
\usepackage{booktabs,array,multirow}
\usepackage{amsfonts,amsmath,amssymb}
\providecommand\citet{\cite}
\providecommand\citep{\cite}
\providecommand\citealt{\cite}
% You can conditionalize code for latexml or normal latex using this.
\newif\iflatexml\latexmlfalse
\providecommand{\tightlist}{\setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}%
\AtBeginDocument{\DeclareGraphicsExtensions{.pdf,.PDF,.eps,.EPS,.png,.PNG,.tif,.TIF,.jpg,.JPG,.jpeg,.JPEG}}
\usepackage[utf8]{inputenc}
\usepackage[greek,english]{babel}
\begin{document}
\title{Principal Manifolds and Nonlinear Dimension Reduction Via Local Tangent
Space Alignment}
\author[ ]{Shouyang Dong}
\author[ ]{Thomas}
\affil[ ]{}
\vspace{-1em}
\date{}
\begingroup
\let\center\flushleft
\let\endcenter\endflushleft
\maketitle
\endgroup
\section*{\texorpdfstring{Introduction\\
}{Introduction }}\label{introduction}
Principal Manifolds and Nonlinear Dimension Reduction Via Local Tangent
Space Alignment is a article published
in~\href{http://www.siam.org/}{Society for Industrial and Applied
Mathematics}~on July 25th, 2006. The focus for this society is applied,
computational and industrial mathematics. It is composed of people from
a wide variety of vocations. Its members
include~\href{https://en.wikipedia.org/wiki/Engineers}{engineers},~\href{https://en.wikipedia.org/wiki/Scientists}{scientists},
industrial mathematicians, and academic mathematicians. The society is
active in promoting the use of analysis
and~\href{https://en.wikipedia.org/wiki/Mathematical_model}{modeling}~in
all settings. The society also strives to support and provide guidance
to educational institutions wishing to
promote~\href{https://en.wikipedia.org/wiki/Applied_mathematics}{applied
mathematics{[}1{]}}. This article is written
by~\href{http://epubs.siam.org/author/Zhang\%2C+Zhenyue}{Zhenyue
Zhang}~and~\href{http://epubs.siam.org/author/Zha\%2C+Hongyuan}{Hongyuan
Zha}. Professor Zhenyue Zhang is from department of Mathematics,
Zhejiang University, while professor Hongyuan Zha comes from department
of Computer Science and Engineering in Pennsylvania State University.~\\
In this article, first it introduces local tangent space alignment(LTSA)
algorithm to modeled high-dimensional data by using low-dimensional
nonlinear manifold in section 1. Second it formulates the problem of
manifold learning and dimension reduction, and illustrates the intricacy
of the problem using the linear case in section 2. In section 3 it
discusses the issue of learning local geometry by using tangent space.
Next in section 4, it shows how to align those local tangent spaces in
order to learn the global coordinate system of the underlying manifold.
It discusses how to construct the manifold once the global coordinate
system is available in section 5. Then it presents an error analysis of
LTSA in section 6. In section 7, it shows how the partial
eigen-decomposition used in global coordinate construction could be
efficiently computed. Then it presents a collection of numerical
experiments in section 8. Finally in section 9, it concludes the paper
and addresses several theoretical and algorithmic issues for further
research and improvements\protect\hyperlink{_edn2}{{[}2{]}}.~\\
\subsection*{\texorpdfstring{Background of the Article ~\\
}{Background of the Article ~ }}\label{background-of-the-article}
Nowadays many high-dimensional data in real-world applications can be
modeled as data points lying close to a low-dimensional nonlinear
manifold. However, discovering the structure of the manifold from a set
of data points sampled from the manifold possibly with noise is a very
challenging unsupervised learning\protect\hyperlink{_edn3}{{[}3{]}}.
Traditional dimension reduction techniques work well when the data
points lie close to a linear subspace, however, it failed to detect
nonlinear structures of the set of data points, such as principal
component analysis and factor analysis. To solve this problem, there
have been much renewed interests in developing efficient algorithms for
constructing nonlinear low-dimensional manifolds from sample data points
in high-dimensional manifold, emphasizing simple algorithmic
implementation and avoiding optimization problems prone to local
minimal\protect\hyperlink{_edn4}{{[}4{]}}-\protect\hyperlink{_edn7}{{[}7{]}},
nevertheless many fundamental problems are required to be further
investigated. ~\\
Then the authors got inspiration from and improved upon the previous
work, used the tangent space in the neighborhood of a data point to
represent the local geometry. Then aligned those local tangent spaces to
construct the global coordinate system for the nonlinear manifold.\\
\subsubsection*{\texorpdfstring{Positioning~\\
}{Positioning~ }}\label{positioning}
Several different algorithms have been developed to perform dimension
reduction of low-dimensional nonlinear manifolds embedded in a high
dimensional space. For example,
~Isomap\protect\hyperlink{_edn8}{{[}8{]}}~was originally proposed as a
generalization of multi-dimensional scaling. An alternative method known
as locally linear embedding (LLE){[}4{]}was developed that solved a
consecutive pair of linear least square optimizations. More recently,
another method for dimensionality reduction of manifolds has been
described in terms of the spectral decomposition of graph
Laplacians\protect\hyperlink{_edn9}{{[}9{]}}. Although all three
algorithms, Isomap, graph Laplacian eigenmaps, and LLE have quite
different motivations and derivations, they all can perform
dimensionality reduction on nonlinear manifolds. The author got the
inspiration from these pioneering work and then made some
improvements{[}4-5{]}, it opened up new directions in nonlinear manifold
learning, although many fundamental problems were required to be further
investigated.~\\
\paragraph{\texorpdfstring{Contributions~~\\
}{Contributions~~ }}\label{contributions}
Though not technically a variant of LLE, Local tangent space alignment
(LTSA) is algorithmically similar enough to LLE that it can be put in
this category. Rather than focusing on preserving neighborhood distances
as in LLE, LTSA seeks to characterize the local geometry at each
neighborhood via its tangent space, and performs a global optimization
to align these local tangent spaces to learn the embedding. In general,
LTSA is less sensitive to the choice of k neighborhoods as compared to
LLE. LTSA performs eigen-decomposition on a per point basis, rather than
applying on the entire sparse matrix which highly reduces the
computational complexity. It is fast as well as adaptive to complex
nonlinear manifolds. Hence LTSA has been successfully applied to
microarray data analysis\protect\hyperlink{_edn10}{{[}10{]}}and face
recognition\protect\hyperlink{_edn11}{{[}11{]}}.~\\
\textbf{Experiments}\\
\subparagraph{\texorpdfstring{\\
}{ }}\label{section}
In order to illustrate the performance of LTSA algorithm, this article
presents several numerical examples. First it tests the LTSA method for
1D manifold with uniformly sampled coordinates in a interval. In all
those cases, it adds Gaussian noise to obtain the data
set\(\left\{ {{x_i}} \right\}\),which is~\\
\({x_i} = f\left( {x_i^*} \right) + \eta randn\left( {m,1} \right)\)\\
where m is the dimension of the input space, and randn is the Matlab's
standard normal distribution,~is the noise.\\
It gave the following three one-variable functions\\
\(f\left( \tau \right) = {\left( {10\tau ,10{\tau ^3} + 2{\tau ^2} - 10\tau } \right)^T},\tau \in \left[ { - 1,1} \right],\eta = 0.1\)\\
\(f\left( \tau \right) = {\left( {\tau \cos \left( \tau \right),\tau \sin \left( \tau \right)} \right)^T},\tau \in \left[ {0,4\pi } \right],\eta = 0.2\)\\
\(f\left( \tau \right) = {\left( {3\cos \left( \tau \right),3\sin \left( \tau \right),3\tau } \right)^T},\tau \in \left[ {0,4\pi } \right],\eta = 0.2\)\\
then plotted the color-coded sample data points as following Fig1\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.00\columnwidth]{figures/Tu-Pian--2/Tu-Pian--2}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--9/Tu-Pian--9}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--10/Tu-Pian--10}
\end{center}
\end{figure}
\textbf{Fig 1 Sample data points with noise from various 1-D
manifold(top) and coordinates of computed}
\textbf{~\({\tau _i}\)~and exact}
\(\tau _i^*\)\textbf{~(bottom).}\\
In the second row of figure
1,~\(\tau _i^*\)against~\({\tau _i}\)~are plotted,
where~\({\tau _i}\)'s are the computed coordinates by LTSA. From
these figures,~\(\left( {\tau _i^*,{\tau _i}} \right)\)~forms a straight line with either
a~\(\frac{\pi}{4}\)~and~\(-\frac{\pi}{4}\)~slope. Because it is
difficult to align the locale tangent information if some of the
matrix~\({P_i}'s\)~are close to be singular. The computed
coordinates~\({\tau _i}\)~and its neighbors maybe compressed
together.~\\
Then to clearly demonstrate this phenomenon, it gave the following
function,\\
\(f\left( t \right) = {\left[ {{{\cos }^3}\left( \tau \right),{{\sin }^3}\left( \tau \right)} \right]^T},\tau \in \left[ {0,\pi } \right]\)\\
When~\(\tau = \pi /2\), then~~\({\tau _i}'s\)become very small, all
compress to a small interval around zero. So it gave another 1D curve
defined by\\
~\(f\left( t \right) = {\left[ {10\cos \left( \tau \right),\sin \left( \tau \right)} \right]^T},\tau \in \left[ {\pi /2,3\pi /2} \right]\)\\
When the point~~\(\tau = \pi\)where the curvature is very large, it
has similar phenomenon as the upper equation, the
computed~\({\tau _i}'s\)~near the corresponding also become very
small as shown in Fig 2.\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--13/Tu-Pian--13}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--3-Shang-Wu-3.23.42/Tu-Pian--3-Shang-Wu-3.23.42}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--27/Tu-Pian--27}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Fig 2. 1-D manifolds with singular
points (left) and corresponding coordinates}
\textbf{~\({\tau _i}\)~via exact \(\tau _i^*\)~(right).}\\
Next the article discusses about the issues of the interaction density
and noise levels. It plots the computed results for the generating
function\\
\(f\left( t \right) = 3{\tau ^3} + 2{\tau ^2} - 2\tau ,\tau \in \left[ { - 1.1,1} \right]\)\\
the data set was generated by adding noise in a relative fashion,\\
\({x_i} = f\left( {{\tau _i}} \right)\left( {1 + \eta {\varepsilon _i}} \right)\)\\
where~\({{\varepsilon _i}}\)~is the normal distribution, then it
compares~\({\eta = 0.01,0.03,0.05}\)\({x_i}\)with
\selectlanguage{greek}η\selectlanguage{english}=0.01,0.03,0.0~respectively. Here I plot the there figures in the first
raw of Fig3. For the data sets, they used the same number of neighbors,
which is k=10. With the increasing noise level~, the
computed~\({{\tau _i}}\)'s get expressed at points with relatively
large noise. The quality of the computed~'s can be improved if it
increases the number of neighbors as shown on the column (d) in Fig3\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--16/Tu-Pian--16}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--17/Tu-Pian--17}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ Fig 3 1-D manifolds with different noise levels
(top) and computed coordinates \({\tau _i}\)}~\textbf{vs
exact}~\(\tau _i^*\)\textbf{~(bottom).}\\
In the Fig 3, it showed that different neighborhood size k produced
different embedding results. Few neighbors used may result a
rank-deficient tangent space and leads to over-fitting, while a large
neighborhood introduced too much bias and the computed tangent space
would not much the local geometry well. Hence it is worthy of
considering variable number of neighbors that are adaptively chosen at
each data point. Fortunately, our LTSA algorithm seems to be less
sensitive to the choice of k than LLE does as will be shown later.~\\
Then applied both LTSA and LLE to the Swissroll data set (Fig 4) and
Helix data set(Fig 7)(total data is 2000 and k which is chosen from k =
6 to k = 30, LTSA always produces coordinates that has similar geometric
structure as the generating coordinates. There are little geometric
deformations in the coordinates generated by LTSA, see Figure 6. In
Figure 5, we plot the results for LLE, the deformations (stretching and
compression) in the generated coordinates are quite prominent. Similar
results are plotted for the Helix data set{[}7{]}in Figure 7 (LLE) and
Figure 8 (LTSA). Both of these two surfaces have zero Gaussian
curvature, and therefore they can be flattened without any geometric
deformation, i.e., the two surfaces are isometric to a 2D plane.\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--18/Tu-Pian--18}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Fig 4 The figure of Swissroll}\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--19/Tu-Pian--19}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--20/Tu-Pian--20}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~Fig 5 Computed 2D coordinates of
the Swissroll by LLE with various neighborhood size k}\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--21/Tu-Pian--21}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~Fig 6 Computed coordinates of the
Swissroll by LTSA with various neighborhood size k.}\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--22/Tu-Pian--22}
\end{center}
\end{figure}\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--29/Tu-Pian--29}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Fig 7 Computed 2D coordinates of
the Helix by LLE with various neighborhood size k.}\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--28/Tu-Pian--28}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~Fig 8 Computed 2D coordinates
of Helix by LTSA with various neighborhood size k}\\
Now I apply LTSA to a 2-D manifold embedded in a 100 dimensional space.
The data points are generated as follows. First we generate N = 5000 3D
points,~\\
\({x_i} = {\left( {{t_i},{s_i},h\left( {{t_i},{s_i}} \right)} \right)^T} + 0.01{\eta _i}\)\\
with~\({{t_i}}\)~and~\({{s_i}}\)~uniformly distributed in
the interval {[}-1, 1{]}, the~'s are standard normal.
The~\({h\left( {{t_i},{s_i}} \right)}\)~is a peak function defined by\\
\(h\left( {t,s} \right) = 0.3{\left( {1 - t} \right)^2}{e^{ - {t^2} - {{\left( {s + 1} \right)}^2}}} - \left( {0.2t - {t^3} - {s^5}} \right){e^{ - {t^2} - {s^2}}} - 0.1{e^{ - {{\left( {t + 1} \right)}^2} - {s^2}}}\)\\
This function is plotted in the left of Figure 9.\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--25/Tu-Pian--25}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Fig 9 2-D
manifold in a 100-D space generated by 3-D peak function}\\
One advantage of LTSA over LLE is that using LTSA we can potentially
detect the intrinsic dimension of the underlying manifold by analyzing
the local tangent space structure. In particular, we can examine the
distribution of singular values of the data
matrix~\({X_i}\)~consisting of the data points in the
neighborhood of each data point~\({X_i}\). If the manifold is
of dimension d, then~\({X_i}\)~will be close to a rank-d
matrix.~\\
Next, I discuss the issue of how to use the global
coordinates~\({\tau _i}\)'s as a means for clustering the data
points~\({X_i}\)'s. The situation is illustrated by Fig10. The
data set consists of five bivariate Gaussians with covariance matrices
0.2I.~\\
There are 200 sample points from each Gaussian. The thick curve on the
right panel represents the principal curve computed by LTSA and the thin
curve by LLE. It is seen that the thick curve goes through each of the
Gaussians in turn, and the corresponding global coordinates (plotted in
the right panel) clearly separate the three Gaussians. LLE did not
perform as well, mixing four of the Gaussians.\\\selectlanguage{english}
\begin{figure}[h!]
\begin{center}
\includegraphics[width=0.70\columnwidth]{figures/Tu-Pian--26/Tu-Pian--26}
\end{center}
\end{figure}
\textbf{~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Fig 10 (left) The 3D cluster,
(middle)global coordinates by LLE, (right) global coordinates by LTSA}\\
Conclusion\\
A new algorithm(LTSA) was proposed in this article for nonlinear
manifold learning and nonlinear dimension reduction. The author used
construction of local tangent spaces to represent local geometry and the
global alignment of the local tangent spaces to obtain the the global
coordinate system for the underlying manifold. Then it provided some
error analysis to exhibit the interplay of approximation accuracy,
sampling density, noise level and curvature structure of the manifold.
At the same time, it compared LTSA with local linear embedding(LLE),
which showed using LTSA can potentially detect the intrinsic dimension
of the underlying manifold by analyzing the local tangent space
structure. Last it listed several issues which deserved further
investigation.\\
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
~ ~ ~ ~ ~ ~ ~ Reference\\
{[}1{]}\href{http://www.siam.org/about/more/overview.php}{\emph{http://www.siam.org/about/more/overview.php}}\\
{[}2{]}Z. Zhang, H. Zha, Principal manifolds and nonlinear dimension
reduc- tion via local tangent space alignment, SIAM J. Sci. Comput. 26
(2004) 313--338.\\
{[}3{]}T. Kohonen.~\emph{Self-organizing Maps}. Springer-Verlag, 3rd
Edition, 2000\\
{[}4{]}S. Roweis and L.Saul. Nonlinear dimension reduction by locally
linear embedding.~\emph{Science}, 290: 2323-2326, 2000\\
{[}5{]}L.Saul and S. Roweis. Think globally, fit locally: unsupervised
learning of nonlinear manifolds. Technical Reports, MS CIS-02-18, Univ.
Pennsylvania, 2002.\\
{[}6{]}Y. The and S. Roweis. Automatic Alignment of Hidden
Representations. To appear in~\emph{Advances in Neural Information
Processing Systems}, 15, MIT Press (2003).\\
{[}7{]}J. Tenenbaum, V. De Silva and J. Langford. A global geometric
framework for nonlinear dimension reduction.~\emph{Science},
290:2319-2323, 2000.\\
{[}8{]} J.B. Tenenbaum, V. de Silva, and J.C. Langford. A global
geometric framework for nonlinear~\\
dimensionality reduction.~\emph{Science}, 290(5500):2319--2323, 2000.~\\
{[}9{]}M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality
reduction and data representation.~\emph{Neural Computation},
(15):1373--1396, 2003.~\\
{[}10{]}Teng, L.~\emph{et al.}~Dimension reduction of microarray data
based on local tangent space alignment. Fourth IEEE Conference on
Cognitive Informatics 2005, ICCI 2005. Irvine, CA, United states,
Institute of Electrical and Electronics Engineers Computer Society
(2005, 7 31).\\
{[}11{]} Lei, Y. K. Feature extraction using orthogonal discriminant
local tangent space alignment.~\emph{Pattern Anal Appl}~15, 249--259.
(2011).
\selectlanguage{english}
\FloatBarrier
\end{document}