Browse Teach Curate

Johnson-Lindenstrauss Lemma for Dimensionality Reduction

The classical result that any d points in a high-dimensional Euclidean space can be linearly embedded into O(log d / eps^2) dimensions, via a random projection, while preserving all pairwise distances up to a factor 1+eps. The note uses this lemma directly as the starting embedding it then discretizes.

Default Guide Video

Johnson-Lindenstrauss Lemma for Dimension Reduction

The Johnson-Lindenstrauss lemma states that any set of n points in a high-dimensional Euclidean space (R^d with the l2 metric) can be embedded via a linear map into a much lower-dimensional space R^m…