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

**Authors:** Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, Mark Crowley  
**arXiv:** [2108.04172](https://arxiv.org/abs/2108.04172)  
**Date:** 2021-08-09  
**Summary page:** https://www.summarizepaper.com/en/arxiv-id/2108.04172v1/

## Key points

- The paper provides an overview of the Johnson-Lindenstrauss (JL) lemma and techniques related to linear and nonlinear random projections.
- Linear random projection is justified through the JL lemma, with discussions on sparse random projections using $\ell_1$ norm and interpolation norm.
- Two key applications highlighted are low-rank matrix approximation and approximate nearest neighbor search achieved through random projection onto hypercube.
- Advanced methods for nonlinear random projection include Random Fourier Features (RFF) and Random Kitchen Sinks (RKS).
- Other techniques for nonlinear random projection mentioned are extreme learning machine, randomly weighted neural networks, and ensemble of random projections.

## Summary

, , , , 

The paper titled "Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey" by authors Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley provides a comprehensive overview of the Johnson-Lindenstrauss (JL) lemma and various techniques related to linear and nonlinear random projections. The paper begins by discussing linear random projection and its justification through the JL lemma and its proof. It then delves into sparse random projections utilizing $\ell_1$ norm and interpolation norm. The authors highlight two key applications of random projection: low-rank matrix approximation and approximate nearest neighbor search achieved through random projection onto hypercube. Moreover, the paper explores advanced methods for nonlinear random projection such as Random Fourier Features (RFF) and Random Kitchen Sinks (RKS). Additionally, it introduces other techniques for nonlinear random projection including extreme learning machine, randomly weighted neural networks, and ensemble of random projections. Overall, this tutorial serves as a valuable resource for understanding the theoretical foundations and practical applications of random projections in various machine learning tasks. The insights provided by the authors pave the way for further exploration in dimensionality reduction and manifold learning.