Related: “clustering”? Also with the notion of similarity as seen in kernel tricks. Inducing a differential metric. Matrix factorisations and random features, highdimensional statistics and discuss random projections and their role in compressed sensing etc.
misc
Dimensionality reduction 101: linear algebra, hidden variables and generative models
Diffusion maps: another way of mapping graphs to \(\mathbb{R}^d\).
PCA and cousins
Kernel PCA, linear algebra and probabilistic formulations.
Linear algebra version of PCA puts us in the world of matrix factorisationa.
Nonlinear versions

Principal component analysis (PCA) is one of the most versatile tools for unsupervised learning with applications ranging from dimensionality reduction to exploratory data analysis and visualization. While much effort has been devoted to encouraging meaningful representations through regularization (e.g. nonnegativity or sparsity), underlying linearity assumptions can limit their effectiveness. To address this issue, we propose Additive Component Analysis (ACA), a novel nonlinear extension of PCA. Inspired by multivariate nonparametric regression with additive models, ACA fits a smooth manifold to data by learning an explicit mapping from a lowdimensional latent space to the input space, which trivially enables applications like denoising. Furthermore, ACA can be used as a dropin replacement in many algorithms that use linear component analysis methods as a subroutine via the local tangent space of the learned manifold. Unlike many other nonlinear dimensionality reduction techniques, ACA can be efficiently applied to large datasets since it does not require computing pairwise similarities or storing training data during testing. Multiple ACA layers can also be composed and learned jointly with essentially the same procedure for improved representational power, demonstrating the encouraging potential of nonparametric deep learning. We evaluate ACA on a variety of datasets, showing improved robustness, reconstruction performance, and interpretability.
Autoencoder and word2vec
“The nonlinear PCA” interpretation, I just heard from Junbin Gao.
\[L(x, x') = \xx\^2=\x\sigma(U*sigma*W^Tx+b)) + b')\^2\]
Locality Preserving projections
Try to preserve the nearness of points if they are connected on some (weight) graph.
\[\sum_{i,j}(y_iy_j)^2 w_{i,j}\]
So we seen an optimal projection vector.
(requirement for sparse similarity matrix?)
Multidimensional scaling
TDB
Topological data analysis
Start with the distances between points and try to find a lower dimensional manifold which preserves their distances. Local MDS? TDB.
Random projection
Stochastic neighbour embedding
Probabilisitically preserving closeness.
Refs
 SoVM14: C. O. S. Sorzano, J. Vargas, A. Pascual Montano (2014) A survey of dimensionality reduction techniques. ArXiv:1403.2877 [Cs, qBio, Stat].
 HaCL06: R. Hadsell, S. Chopra, Y. LeCun (2006) Dimensionality Reduction by Learning an Invariant Mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2, pp. 1735–1742). DOI
 WDLS09: Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, Josh Attenberg (2009) Feature Hashing for Large Scale Multitask Learning. In Proceedings of the 26th Annual International Conference on Machine Learning (pp. 1113–1120). New York, NY, USA: ACM DOI
 SaHi07: Ruslan Salakhutdinov, Geoff Hinton (2007) Learning a Nonlinear Embedding by Preserving Class Neighbourhood Structure. In PMLR (pp. 412–419).
 SoLe12: Kihyuk Sohn, Honglak Lee (2012) Learning Invariant Representations with Local Transformations. In Proceedings of the 29th International Conference on Machine Learning (ICML12) (pp. 1311–1318).
 WHGS17: Boyue Wang, Yongli Hu, Junbin Gao, Yanfeng Sun, Haoran Chen, Baocai Yin (2017) Locality Preserving Projections for Grassmann manifold. In PRoceedings of IJCAI, 2017.
 GlRo06: Amir Globerson, Sam T. Roweis (2006) Metric learning by collapsing classes. In Advances in neural information processing systems (pp. 451–458). Cambridge, MA, USA: MIT Press
 Cook18: R. Dennis Cook (2018) Principal Components, Sufficient Dimension Reduction, and Envelopes. Annual Review of Statistics and Its Application, 5(1), 533–559. DOI
 LSSG14: David LopezPaz, Suvrit Sra, Alex Smola, Zoubin Ghahramani, Bernhard Schölkopf (2014) Randomized Nonlinear Component Analysis. ArXiv:1402.0119 [Cs, Stat].
 HiSa06: Geoffrey E. Hinton, Ruslan R. Salakhutdinov (2006) Reducing the dimensionality of data with neural networks. Science, 313(5786), 504–507. DOI
 SWMS99: Alex J. Smola, Robert C. Williamson, Sebastian Mika, Bernhard Schölkopf (1999) Regularized Principal Manifolds. In Computational Learning Theory (pp. 214–229). Springer Berlin Heidelberg
 PeLV14: Diego H. PeluffoOrdónez, John A. Lee, Michel Verleysen (2014) Short review of dimensionality reduction methods based on stochastic neighbour embedding. In Advances in SelfOrganizing Maps and Learning Vector Quantization (pp. 65–74). Springer
 HiRo02: Geoffrey Hinton, Sam Roweis (2002) Stochastic Neighbor Embedding. In Proceedings of the 15th International Conference on Neural Information Processing Systems (pp. 857–864). Cambridge, MA, USA: MIT Press
 Wass18: Larry Wasserman (2018) Topological Data Analysis. Annual Review of Statistics and Its Application, 5(1), 501–532. DOI
 OyTr15: Samet Oymak, Joel A. Tropp (2015) Universality laws for randomized dimension reduction, with applications. ArXiv:1511.09433 [Cs, Math, Stat].
 GBTE14: Ross Goroshin, Joan Bruna, Jonathan Tompson, David Eigen, Yann LeCun (2014) Unsupervised Learning of Spatiotemporally Coherent Metrics. ArXiv:1412.6056 [Cs].
 MaHi08: Laurens van der Maaten, Geoffrey Hinton (2008) Visualizing data using tSNE. Journal of Machine Learning Research, 9(Nov), 2579–2605.