Optimal Bounds for Johnson-Lindenstrauss Transformations

zbMath1480.46016arXiv1803.05350MaRDI QIDQ4614115

Michael A. Burr, Fiona Knoll, Shuhong Gao

Publication date: 30 January 2019

Full work available at URL: https://arxiv.org/abs/1803.05350

zbMATH Keywords

dimension reductionphase transitionasymptotic thresholdJohnson-Lindenstrauss transformation

Mathematics Subject Classification ID

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

Related Items (2)

Covariance matrix testing in high dimension using random projections ⋮ Random Projection Ensemble Classification with High-Dimensional Time Series

Cites Work

• Unnamed Item
• The restricted isometry property and its implications for compressed sensing
• The Johnson-Lindenstrauss lemma and the sphericity of some graphs
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Problems and results in extremal combinatorics. I.
• An algorithmic theory of learning: Robust concepts and random projection
• A sparse Johnson
• Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
• Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Subconstant Error
• Almost Optimal Explicit Johnson-Lindenstrauss Families
• Low-Rank Approximation and Regression in Input Sparsity Time
• Sparser Johnson-Lindenstrauss Transforms
• A Remark on Stirling's Formula
• Extensions of Lipschitz mappings into a Hilbert space
• On variants of the Johnson–Lindenstrauss lemma
• Low rank approximation and decomposition of large matrices using error correcting codes
• An elementary proof of a theorem of Johnson and Lindenstrauss
• A fast and efficient algorithm for low-rank approximation of a matrix

This page was built for publication: Optimal Bounds for Johnson-Lindenstrauss Transformations