Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey

Abstract

This is a tutorial and survey paper on the Johnson-Lindenstrauss (JL) lemma and linear and nonlinear random projections. We start with linear random projection and then justify its correctness by JL lemma and its proof. Then, sparse random projections with ${\ell }_1$ norm and interpolation norm are introduced. Two main applications of random projection, which are low-rank matrix approximation and approximate nearest neighbor search by random projection onto hypercube, are explained. Random Fourier Features (RFF) and Random Kitchen Sinks (RKS) are explained as methods for nonlinear random projection. Some other methods for nonlinear random projection, including extreme learning machine, randomly weighted neural networks, and ensemble of random projections, are also introduced.

arXiv commentTo appear as a part of an upcoming textbook on dimensionality reduction and manifold learning

References in corpus (8)

• Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?
• The Theory Behind Overfitting, Cross Validation, Regularization, Bagging, and Boosting: Tutorial
• Recovering the Optimal Solution by Dual Random Projection
• Optimal Rates for Random Fourier Features
• A survey of dimensionality reduction techniques based on random projection
• Unsupervised and Supervised Principal Component Analysis: Tutorial
• Fisher and Kernel Fisher Discriminant Analysis: Tutorial
• Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nyström Method, and Use of Kernels in Machine Learning: Tutorial and Survey

Cited by in corpus (2)

• Parsimonious Physics-Informed Random Projection Neural Networks for Initial-Value Problems of ODEs and index-1 DAEs
• Generative Adversarial Networks and Adversarial Autoencoders: Tutorial and Survey