Lower Bounds for Oblivious Subspace Embeddings

DOI10.1007/978-3-662-43948-7_73zbMath1398.68202arXiv1308.3280OpenAlexW2124155943MaRDI QIDQ5167800

Huy L. Nguyen, Jelani Nelson

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions ⋮ Practical Sketching Algorithms for Low-Rank Matrix Approximation ⋮ Randomized LU decomposition using sparse projections ⋮ Random projections for Bayesian regression ⋮ Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation

This page was built for publication: Lower Bounds for Oblivious Subspace Embeddings