Johnson-Lindenstrauss Lemma, Linear and Nonlinear Random Projections, Random Fourier Features, and Random Kitchen Sinks: Tutorial and Survey
It serves as an educational resource for researchers and practitioners in machine learning and data science, offering a comprehensive overview of established methods without introducing new contributions.
This paper provides a tutorial and survey on the Johnson-Lindenstrauss lemma and random projection methods, covering linear and nonlinear techniques such as Random Fourier Features and Random Kitchen Sinks, with applications in low-rank matrix approximation and nearest neighbor search.
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.