An Introduction to Johnson-Lindenstrauss Transforms

Abstract

Johnson--Lindenstrauss Transforms are powerful tools for reducing the dimensionality of data while preserving key characteristics of that data, and they have found use in many fields from machine learning to differential privacy and more. This note explains what they are; it gives an overview of their use and their development since they were introduced in the 1980s; and it provides many references should the reader wish to explore these topics more deeply.

The text was previously a main part of the introduction of my PhD thesis, but it has been adapted to be self contained and serve as a (hopefully good) starting point for readers interested in the topic

References in corpus (8)

• Circulant and Toeplitz matrices in compressed sensing
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
• Randomness Efficient Fast-Johnson-Lindenstrauss Transform with Applications in Differential Privacy and Compressed Sensing
• SUOD: Toward Scalable Unsupervised Outlier Detection
• Projection-Cost-Preserving Sketches: Proof Strategies and Constructions
• Projection & Probability-Driven Black-Box Attack
• Improving the Johnson-Lindenstrauss Lemma