mlsanityData to 7 Oct 2026

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

arXiv 2108.04172 ↗First posted 9 Aug 2021stat.ML cs.DS cs.LGcited by 8

Not on the map. Why?

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.

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

Builds on

14 of 86 references.

References · 14

  1. 2015On the Error of Random Fourier Featurescited by 76
  2. 2016Optimality of the Johnson-Lindenstrauss Lemmacited by 41
  3. 2015Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy?cited by 40
  4. 2015Optimal Rates for Random Fourier Featurescited by 38
  5. 2021Reproducing Kernel Hilbert Space, Mercer's Theorem, Eigenfunctions, Nystr"om Method, and Use of Kernels in Machine Learning: Tutorial and Surveycited by 36
  6. 2015Random-projection ensemble classificationcited by 29
  7. 2019The Theory Behind Overfitting, Cross Validation, Regularization, Bagging, and Boosting: Tutorialcited by 22
  8. 2013Signal Recovery from Pooling Representationscited by 12
  9. 2019Unsupervised and Supervised Principal Component Analysis: Tutorialcited by 12
  10. 2019Fisher and Kernel Fisher Discriminant Analysis: Tutorialcited by 12
  11. 2017A survey of dimensionality reduction techniques based on random projectioncited by 8
  12. 2013Learning Stable Group Invariant Representations with Convolutional Networkscited by 4
2 more
  1. 2014A unified framework for linear dimensionality reduction in L1cited by 1
  2. 2016Random Feature Maps via a Layered Random Projection (LaRP) Framework for Object Classificationcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 0; 2024: 2; 2025: 2; 2026: 2.

8 papers.

  1. 2024Stochastic Taylor Derivative Estimator: Efficient amortization for arbitrary differential operatorscited by 20
  2. 2025Understanding Dynamic Scenes in Ego Centric 4D Point Cloudscited by 6
  3. 2021Generative Adversarial Networks and Adversarial Autoencoders: Tutorial and Surveycited by 4
  4. 2022On Manifold Hypothesis: Hypersurface Submanifold Embedding Using Osculating Hyperspherescited by 1
  5. 2026Hierarchical SVG Tokenization: Learning Compact Visual Programs for Scalable Vector Graphics Modelingcited by 1
  6. 2024Node Similarities under Random Projections: Limits and Pathological Casescited by 0
  7. 2025Random functions as data compressors for machine learning of molecular processescited by 0
  8. 2026Stochastic Dimension Zeroth-Order Estimator: Stable and Memory-Efficient Training of PINNscited by 0