Geometric structure of high-dimensional data and dimensionality reduction

《高维数据几何结构与降维(英文版)》

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 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

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 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

6.2 euclidean metric 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 algorithm

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 factorization

15.1.1 rank-revealing factorization

15.1.2 fast rank-revealing algorithms

15.1.3 nystrsm 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