Front Matter
  Chapter 1 Introduction
   1.1 Overview of Dimensionality Reduction
   1.2 High Dimension Data Acquisition
    1.2.1 Collection of Images in Face Recognition
    1.2.2 Handwriting Letters and Digits
    1.2.3 Text Documents
    1.2.4 Hyperspectral Images
   1.3 Curse of the Dimensionality
    1.3.1 Volume of Cubes and Spheres
    1.3.2 Volume of a Thin Spherical Shell
    1.3.3 Tail Probability of the Multivariate Gaussian Distributions
    1.3.4 Diagonals of Cube
    1.3.5 Concentration of Norms and Distances
   1.4 Intrinsic and Extrinsic Dimensions
    1.4.1 Intrinsic Dimension Estimation
    1.4.2 Correlation Dimension
    1.4.3 Capacity Dimension
    1.4.4 Multiscale Estimation
   1.5 Outline of the Book
    1.5.1 Categories of DR Problems
    1.5.2 Scope of This Book
    1.5.3 Other Topics Related to This Book
    1.5.4 Arti¯cial Surfaces for Testing DR Algorithms
   References
 Part I Data Geometry
  Chapter 2 Preliminary Calculus on Manifolds
   2.1 Linear Manifold
    2.1.1 Subspace and Projection
    2.1.2 Functions on Euclidean Spaces
    2.1.3 Laplace Operator and Heat Diffusion Kernel
   2.2 Differentiable Manifolds
    2.2.1 Coordinate Systems and Parameterization
    2.2.2 Tangent Spaces and Tangent Vectors
    2.2.3 Riemannian Metrics
    2.2.4 Geodesic Distance
   2.3 Functions and Operators on Manifolds
    2.3.1 Functions on Manifolds
    2.3.2 Operators on Manifolds
   References
  Chapter 3 Geometric Structure of High-Dimensional Data
   3.1 Similarity and Dissimilarity of Data
    3.1.1 Neighborhood De¯nition
    3.1.2 Algorithms for Construction of Neighborhood
   3.2 Graphs on Data Sets
    3.2.1 Undirected Graphs
    3.2.2 Directed Graphs
    3.2.3 Neighborhood and Data Graphs
   3.3 Spectral Analysis of Graphs
    3.3.1 Laplacian of Graphs
    3.3.2 Laplacian on Weighted Graphs
    3.3.3 Contracting Operator on Weighted Graph
   References
  Chapter 4 Data Models and Structures of Kernels of DR
   4.1 Data Models in Dimensionality Reduction
    4.1.1 Input Data of First Type
    4.1.2 Input Data of Second Type
    4.1.3 Constraints on Output Data
    4.1.4 Consistence of Data Graph
    4.1.5 Robust Graph Connection Algorithm
   4.2 Constructions of DR Kernels
    4.2.1 DR Kernels of Linear Methods
    4.2.2 DR Kernels of Nonlinear Methods
    4.2.3 Conclusion
   References
 Part II Linear Dimensionality Reduction
  Chapter 5 Principal Component Analysis
   5.1 Description of Principal Component Analysis
    5.1.1 Geometric Description of PCA
    5.1.2 Statistical Description of PCA
   5.2 PCA Algorithms
    5.2.1 Matlab Code for PCA Algorithm
    5.2.2 EM-PCA Algorithm
    5.2.3 Testing PCA Algorithm on Arti¯cial Surfaces
   5.3 Applications of PCA
    5.3.1 PCA in Machine Learning
    5.3.2 PCA in Eigenfaces
    5.3.3 PCA in Hyperspectral Image Analysis
   References
  Chapter 6 Classical Multidimensional Scaling
   6.1 Introduction of Multidimensional Scaling
    6.1.1 Data Similarities and Con¯guration
    6.1.2 Classi¯cation of MDS
   6.2 Euclidean Matric and Gram Matrices
    6.2.1 Euclidean Distance Matrices
    6.2.2 Gram Matrix on Data Set
    6.2.3 Relation between Euclidean Distance and Gram Matrix
   6.3 Description of Classical Multidimensional Scaling
    6.3.1 CMDS Method Description
    6.3.2 Relation between PCA and CMDS
    6.3.3 Weighted Graphic Description of CMDS
   6.4 CMDS Algorithm
   References
  Chapter 7 Random Projection
   7.1 Introduction
    7.1.1 Lipschitz Embeddings
    7.1.2 JL-Embeddings
   7.2 Random Projection Algorithms
    7.2.1 Random Matrices and Random Projection
    7.2.2 Random Projection Algorithms
   7.3 Justi¯cation
    7.3.1 Johnson and Lindenstrauss Lemma
    7.3.2 Random Projection based on Gaussian Distribution
    7.3.3 Random Projection based on Types 2 and 3
   7.4 Applications of Random Projections
    7.4.1 Face Recognition Experiments with Random Projection
    7.4.2 RP Applications to Image and Text Data
   References
 Part III Nonlinear Dimensionality Reduction
  Chapter 8 Isomaps
   8.1 Isomap Embeddings
    8.1.1 Description of Isomaps
    8.1.2 Geodesic Metric on Discrete Set
    8.1.3 Isomap Kernel and its Constant Shift
   8.2 Isomap Algorithm
    8.2.1 Algorithm Description
    8.2.2 Matlab Code of Isomap
   8.3 Dijkstra's Algorithm
    8.3.1 Description of Dijkstra's Algorithm
    8.3.2 Matlab Code of Dijkstra's Algorithm
   8.4 Experiments and Applications of Isomaps
    8.4.1 Testing Isomap Algorithm on Arti¯cial Surfaces
    8.4.2 Isomap Algorithm in Visual Perception
    8.4.3 Conclusion
   8.5 Justi¯cation of Isomap Methods
    8.5.1 Graph Distance, S-distance, and Geodesic Distance
    8.5.2 Relation between S-distance and Geodesic Distance
    8.5.3 Relation between S-distance and Graph Distance
    8.5.4 Main Result
   References
  Chapter 9 Maximum Variance Unfolding
   9.1 MVU Method Rescription
    9.1.1 Description of the MVU Method
    9.1.2 MVU Algorithm
   9.2 Semide¯nity Programming
    9.2.1 CSDP
    9.2.2 SDPT3
   9.3 Experiments and Applications of MVU
    9.3.1 Testing MVU Algorithm on Arti¯cial Surfaces
    9.3.2 MVU Algorithm in Sensor Localization
   9.4 Landmark MVU
    9.4.1 Description of Landmark MVU
    9.4.2 Linear Transformation from Landmarks to Data Set
    9.4.3 Algorithm for Landmark Linear Transformation
    9.4.4 Construction of Kernel of Landmark MVU
    9.4.5 Experiments of LMVU
    9.4.6 Conclusion
   References
  Chapter 10 Locally Linear Embedding
   10.1 Description of Locally Linear Embedding
    10.1.1 Barycentric Coordinates
    10.1.2 LLE Method
    10.1.3 LLE Algorithm
   10.2 Experiments and Applications of LLE
    10.2.1 Experiments on Arti¯cial Surfaces
    10.2.2 Conclusion
   10.3 Applications of LLE
    10.3.1 LLE in Image Ordering
    10.3.2 Supervised LLE
   10.4 Justi¯cation of LLE
    10.4.1 Invariance Constraint
    10.4.2 Condition for Weight Uniqueness
    10.4.3 Reduction of the DR Data to LLE Model
   References
  Chapter 11 Local Tangent Space Alignment
   11.1 Description of Local Tangent Space Alignment
    11.1.1 Tangent Coordinates and Manifold Coordinates
    11.1.2 Local Coordinate Representation
    11.1.3 Global Alignment
   11.2 LTSA Algorithm
    11.2.1 LTSA Algorithm Description
    11.2.2 Matlab Code of LTSA
   11.3 Experiments of LTSA Algorithm
    11.3.1 Test LTSA on Arti¯cial Surfaces
    11.3.2 Conclusion
   References
  Chapter 12 Laplacian Eigenmaps
   12.1 Description of the Laplacian Eigenmap Method
    12.1.1 Approximation of Laplace-Beltrami Operator
    12.1.2 Discrete form of Laplace-Beltrami Operator
    12.1.3 Minimization Model for DR Data Set
    12.1.4 Construction of General Leigs Kernels
   12.2 Laplacian Eigenmaps Algorithm
    12.2.1 Steps in Leigs Algorithm
    12.2.2 Matlab Code of Leigs Algorithm
   12.3 Implementation of Leigs Algorithm
    12.3.1 Experiments on Arti¯cial Surfaces
    12.3.2 Conclusion
   References
  Chapter 13 Hessian Locally Linear Embedding
   13.1 Description of Hessian Locally Linear Embedding
    13.1.1 Hessian on Manifold
    13.1.2 Hessian on Tangent Space
    13.1.3 Construction of Hessian Functional
    13.1.4 Construct of HLLE DR Kernel
   13.2 HLLE Algorithm
    13.2.1 HLLE Algorithm Description
    13.2.2 Matlab Code of HLLE
   13.3 Implementation of HLLE
    13.3.1 Experiments on Arti¯cial Surfaces
    13.3.2 Conclusion
   References
  Chapter 14 Diffusion Maps
   14.1 Description of DR Method of Diffusion Maps
    14.1.1 Diffusion Operator on Manifold
    14.1.2 Normalization of Diffusion Kernels
   14.2 Diffusion Maps Algorithms
    14.2.1 Dmaps DR Algorithm Description
    14.2.2 Dmaps Algorithm of Graph-Laplacian Type
    14.2.3 Dmaps Algorithm of Laplace-Beltrami Type
    14.2.4 Dmaps Algorithm of Self-tuning Type
   14.3 Implementation of Dmaps for DR
    14.3.1 Implementation of Dmaps of Graph-Laplacian Type
    14.3.2 Implementation of Dmaps of Laplace-Beltrami Type
    14.3.3 Implementation of Dmaps of Self-turning Type
    14.3.4 Conclusion
   14.4 Diffusion Maps and Multiscale Diffusion Geometry
    14.4.1 Construction of General Diffusion Kernels
    14.4.2 Diffusion Distances
    14.4.3 Diffusion Maps as Feature Extractors
   14.5 Implementation of Dmaps for Feature Extraction
    14.5.1 Feature Extracted from 3-dimensional Toroidal Helix
    14.5.2 Reordering Face Images
    14.5.3 Image Parameters Revealing
    14.5.4 Feature Images of Hyperspectral Image Cube
   References
  Chapter 15 Fast Algorithms for DR Approximation
   15.1 Low-rank Approximation and Rank-revealing Factorization
    15.1.1 Rank-revealing Factorization
    15.1.2 Fast Rank-revealing Algorithms
    15.1.3 NystrÄom Approximation
    15.1.4 Greedy Low-rank Approximation
   15.2 Randomized Algorithm for Matrix Approximation
    15.2.1 Randomized Low-rank Approximation
    15.2.2 Randomized Interpolative Algorithm
    15.2.3 Randomized SVD Algorithm
    15.2.4 Randomized Greedy Algorithm
   15.3 Fast Anisotropic Transformation DR Algorithms
    15.3.1 Fast Anisotropic Transformation
    15.3.2 Greedy Anisotropic Transformation
    15.3.3 Randomized Anisotropic Transformation
    15.3.4 Matlab Code of FAT Algorithms
   15.4 Implementation of FAT Algorithms
    15.4.1 FAT DR of Arti¯cial Surfaces
    15.4.2 Application of FAT to Sorting Image Datasets
    15.4.3 Conclusion
   15.5 Justi¯cation
    15.5.1 Main Proof of Theorem
    15.5.2 Lemmas Used in the Proof
   References
 Appendix A Differential Forms and Operators on Manifolds
  A.1 Differential Forms on Manifolds
  A.2 Integral over Manifold
  A.3 Laplace-Beltrami Operator on Manifold
 Index