Optimal bounds for Johnson-Lindenstrauss transformations

MaRDI QIDQ4614115zbMATH OpenFDO

Authors Michael A. Burr, Shuhong Gao, Fiona Knoll

Publication date 30 January 2019

Full work available at URL https://arxiv.org/abs/1803.05350, http://jmlr.csail.mit.edu/papers/v19/18-264.html

zbMATH Keywords

asymptotic thresholddimension reductionJohnson-Lindenstrauss transformationphase transition

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: In 1984, Johnson and Lindenstrauss proved that any finite set of data in a high-dimensional space can be projected to a lower-dimensional space while preserving the pairwise Euclidean distance between points up to a bounded relative error. If the desired dimension of the image is too small, however, Kane, Meka, and Nelson (2011) and Jayram and Woodruff (2013) independently proved that such a projection does not exist. In this paper, we provide a precise asymptotic threshold for the dimension of the image, above which, there exists a projection preserving the Euclidean distance, but, below which, there does not exist such a projection.

Recommendations

• An elementary proof of a theorem of Johnson and Lindenstrauss
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Dimensionality reductions in \(\ell_{2}\) that preserve volumes and distance to affine spaces
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• An almost optimal unrestricted fast Johnson-Lindenstrauss transform

Cites work

• A fast and efficient algorithm for low-rank approximation of a matrix
• A Remark on Stirling's Formula
• A sparse Johnson-Lindenstrauss transform
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• An algorithmic theory of learning: Robust concepts and random projection
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Extensions of Lipschitz mappings into a Hilbert space
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• Low rank approximation and decomposition of large matrices using error correcting codes
• On variants of the Johnson–Lindenstrauss lemma
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Problems and results in extremal combinatorics. I.
• Sparser Johnson-Lindenstrauss transforms
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• The restricted isometry property and its implications for compressed sensing

Cited in

(14)

• Covariance matrix testing in high dimension using random projections
• Old tails and new trails in high dimensions
• An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• On variants of the Johnson–Lindenstrauss lemma
• Tighter bounds for random projections of manifolds
• scientific article; zbMATH DE number 1132946 (Why is no real title available?)
• The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
• An elementary proof of a theorem of Johnson and Lindenstrauss
• The Johnson-Lindenstrauss Transform: An Empirical Study
• Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error
• Random Projection Ensemble Classification with High-Dimensional Time Series
• Holographic phenomenology via overlapping degrees of freedom

This page was built for publication: Optimal bounds for Johnson-Lindenstrauss transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4614115)