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

arXiv: https://arxiv.org/abs/2108.04172 · HTML: https://mlsanity.com/paper/2108.04172/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 86 references that are in the map.
- First posted on arXiv 9 Aug 2021.

## Builds on (most cited first, 14 of 14)

- [On the Error of Random Fourier Features](https://mlsanity.com/paper/1506.02785/) (2015)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?](https://mlsanity.com/paper/1504.08291/) (2015)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Survey](https://mlsanity.com/paper/2106.08443/) (2021)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [The Theory Behind Overfitting, Cross Validation, Regularization, Bagging, and Boosting: Tutorial](https://mlsanity.com/paper/1905.12787/) (2019)
- [Signal Recovery from Pooling Representations](https://mlsanity.com/paper/1311.4025/) (2013)
- [Unsupervised and Supervised Principal Component Analysis: Tutorial](https://mlsanity.com/paper/1906.03148/) (2019)
- [Fisher and Kernel Fisher Discriminant Analysis: Tutorial](https://mlsanity.com/paper/1906.09436/) (2019)
- [A survey of dimensionality reduction techniques based on random projection](https://mlsanity.com/paper/1706.04371/) (2017)
- [Learning Stable Group Invariant Representations with Convolutional Networks](https://mlsanity.com/paper/1301.3537/) (2013)
- [A unified framework for linear dimensionality reduction in L1](https://mlsanity.com/paper/1405.1332/) (2014)
- [Random Feature Maps via a Layered Random Projection (LaRP) Framework for Object Classification](https://mlsanity.com/paper/1602.01818/) (2016)

## Built on by (most cited first, 8 of 8)

- [Stochastic Taylor Derivative Estimator: Efficient amortization for arbitrary differential operators](https://mlsanity.com/paper/2412.00088/) (2024)
- [Understanding Dynamic Scenes in Ego Centric 4D Point Clouds](https://mlsanity.com/paper/2508.07251/) (2025)
- [Generative Adversarial Networks and Adversarial Autoencoders: Tutorial and Survey](https://mlsanity.com/paper/2111.13282/) (2021)
- [On Manifold Hypothesis: Hypersurface Submanifold Embedding Using Osculating Hyperspheres](https://mlsanity.com/paper/2202.01619/) (2022)
- [Hierarchical SVG Tokenization: Learning Compact Visual Programs for Scalable Vector Graphics Modeling](https://mlsanity.com/paper/2604.05072/) (2026)
- [Node Similarities under Random Projections: Limits and Pathological Cases](https://mlsanity.com/paper/2404.10148/) (2024)
- [Random functions as data compressors for machine learning of molecular processes](https://mlsanity.com/paper/2509.17937/) (2025)
- [Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNs](https://mlsanity.com/paper/2603.24002/) (2026)

## Abstract (arXiv)

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