Geometric Structure of High-Dimensional Data and Dimensionality Reduction (English Version) (Chinese Edition)

✍ Scribed by Wang Jian Zhong

• Publisher: Higher Education Press
• Year: 2012
• Tongue: English
• Leaves: 362
• Category: Library

✦ Synopsis

The book introduces different dimensionality reduction methods with their mathematical principles and calculation procedure. Apart typical dimensionality reduction methods, the book pay more attentions to nonlinear method discussions and makes detailed descriptions to nonlinear methods of their main thought, mathematical basis, calculation and procedure which developed in recent period; in addition, the book also introduces dimensionality reduction application on letter distinguishing, face detection, picture segmentation, and data visualization, etc.

✦ Table of Contents

Title Page
Copyright Page
Preface
Table of Contents
Acronyms
Symbols
Chapter 1 Introduction
1.1 Overview of Dimensionality Reduction
Fingerprint identification
Face recognition
Hyperspectral image analysis/processing
Text document classification/search
Data visualization
Data feature extraction
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
Hard dimensionality reduction problems
Soft dimensionality reduction problems
1.5.2 Scope of This Book
Isomap
Maximum Variance Unfolding (MVU)
Locally Linear Embedding (LLE)
Local Tangent Space Alignment (LTSA)
Laplacian Eigenmaps (Leigs)
Hessian Locally Linear Embedding (HLLE)
Diffusion Maps (Dmaps)
1.5.3 Other Topics Related to This Book
Self-organizing map (SOM)
Generative topographic map (GTM)
Autoencoders
Data compression
1.5.4 Artificial 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 Definition
Angular distance
Template distance
Fourier distance
Wavelet distance
Fourier phase distance
Derivative distance
Fourier phase-difference distance
Directionally weighted distance
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 ofKernels 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 DimensionalityReduction
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 Artificial 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 Configuration
6.1.2 Classification of MDS
Metric MDS
Nonmetric MDS
Classical MDS
Replicated MDS
Weighted 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 Justification
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 AlgorithmIn
8.3.2 Matlab Code of Dijkstra’s Algorithm
8.4 Experiments and Applications of Isomaps
8.4.1 Testing Isomap Algorithm on Artificial Surfaces
8.4.2 Isomap Algorithm in Visual Perception
8.4.3 Conclusion
8.5 Justification 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 Semidefinity Programming
9.2.1 CSDP
9.2.2 SDPT3
9.3 Experiments and Applications of MVU
9.3.1 Testing MVU Algorithm on Artificial 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 Artificial Surfaces
10.2.2 Conclusion
10.3 Applications of LLE
10.3.1 LLE in Image Ordering
10.3.2 Supervised LLE
10.4 Justification 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 Artificial 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 Artificial 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 Artificial 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 Fac torization
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 Artificial Surfaces
15.4.2 Application of FAT to Sorting Image Datasets
15.4.3 Conclusion
15.5 Justification
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