On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms

Casper Benjamin Freksen, Kasper Green Larsen

The Johnson-Lindenstrauss lemma is one of the corner stone results in dimensionality reduction. It says that given $N$, for any set of $N$ vectors $X\subset {\mathbb{R}}^n$, there e…