Sparsity lower bounds for dimensionality reducing maps

DOI10.1145/2488608.2488622zbMath1294.68086arXiv1211.0995OpenAlexW2135132414MaRDI QIDQ5495780

Huy L. Nguyen, Jelani Nelson

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

dimensionality reductioncompressed sensingsubspace embeddings

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Sparser Johnson-Lindenstrauss Transforms ⋮ Toward a unified theory of sparse dimensionality reduction in Euclidean space ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Randomized LU decomposition using sparse projections ⋮ Random projections for Bayesian regression ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization

This page was built for publication: Sparsity lower bounds for dimensionality reducing maps