Sparser Johnson-Lindenstrauss Transforms

The Johnson---Lindenstrauss (JL) lemma has led to the development of tools for dealing with datasets in high dimensions. The lemma asserts that a set of high-dimensional points can be projected into lower dimensions, while approximately preserving the ...

The Johnson–Lindenstrauss lemma is one of the cornerstone results in dimensionality reduction. A common formulation of it, is that there exists a random linear mapping $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ such that for any vector $x\in {\mathbb{R}}^n$, f preserves its norm to within $(1\pm \epsilon )$ ...$\mathrm{}$${}^{\mathrm{}}\mathrm{}$$\mathcal{}{}^{\mathrm{}}\mathrm{}$$\mathcal{}{}^{\mathrm{}}{}^{\mathrm{}}\mathrm{}$$$$\mathcal{}$$\mathcal{}{}^{\mathrm{}}\mathrm{}$$\mathcal{}{}^{\mathrm{}}{}^{\mathrm{}}\mathrm{}$${}^{\mathrm{}}{}^{\mathrm{}}\mathrm{}$

Knowledge discovery from big data demands effective representation of data. However, big data are often characterized by high dimensionality, which makes knowledge discovery more difficult. Many techniques for dimensionality reudction have been proposed,...