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.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyghojogh2021johnson

Related papers

• Understanding Sparse JL For Feature Hashing (2019)0.00
• Quantization Algorithms For Random Fourier Features (2021)0.00
• 2-bit Random Projections, Nonlinear Estimators, And Approximate Near Neighbor Search (2016)0.00
• Johnson-lindenstrauss Embeddings For Noisy Vectors -- Taking Advantage Of The Noise (2022)0.00
• Topics In Random Matrices And Statistical Machine Learning (2018)0.00
• Generic LSH Families For The Angular Distance Based On Johnson-lindenstrauss Projections And Feature Hashing LSH (2017)0.00
• Analysis Of Sparsehash: An Efficient Embedding Of Set-similarity Via Sparse Projections (2019)4.52
• OPORP: One Permutation + One Random Projection (2023)2.26