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

This is a tutorial and survey paper on the Johnson-Lindenstrauss (JL) lemma\nand linear and nonlinear random projections. We start with linear random\nprojection and then justify its correctness by JL lemma and its proof. Then,\nsparse random projections with $\\ell_1$ norm and interpolation norm are\nintroduced. Two main applications of random projection, which are low-rank\nmatrix approximation and approximate nearest neighbor search by random\nprojection onto hypercube, are explained. Random Fourier Features (RFF) and\nRandom Kitchen Sinks (RKS) are explained as methods for nonlinear random\nprojection. Some other methods for nonlinear random projection, including\nextreme learning machine, randomly weighted neural networks, and ensemble of\nrandom projections, are also introduced.\n