Lower bounds for oblivious subspace embeddings

DOI10.1007/978-3-662-43948-7_73MaRDI QIDQ5167800zbMATH OpenOpenAlexFDO

Authors Jelani Nelson, Huy L. Nguyen

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

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

Abstract: An oblivious subspace embedding (OSE) for some eps, delta in (0,1/3) and d <= m <= n is a distribution D over R^{m x n} such that for any linear subspace W of R^n of dimension d, Pr_{Pi ~ D}(for all x in W, (1-eps) |x|_2 <= |Pi x|_2 <= (1+eps)|x|_2) >= 1 - delta. We prove that any OSE with delta < 1/3 must have m = Omega((d + log(1/delta))/eps^2), which is optimal. Furthermore, if every Pi in the support of D is sparse, having at most s non-zero entries per column, then we show tradeoff lower bounds between m and s.

Recommendations

• Tight bounds for _p oblivious subspace embeddings
• Nearly tight oblivious subspace embeddings by trace inequalities
• Sparsity lower bounds for dimensionality reducing maps
• Tight bounds for sketching the operator norm, Schatten norms, and subspace embeddings
• Tight bounds for the subspace sketch problem with applications

Cited in

(11)

• Random projections for Bayesian regression
• Randomized LU decomposition using sparse projections
• Nearly tight oblivious subspace embeddings by trace inequalities
• Practical sketching algorithms for low-rank matrix approximation
• Streaming low-rank matrix approximation with an application to scientific simulation
• Tight bounds for _p oblivious subspace embeddings
• Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Low-rank approximation algorithm using sparse projection and its applications
• Subspace embeddings with the rerandomized SRHT
• Optimal oblivious subspace embeddings with near-optimal sparsity

This page was built for publication: Lower bounds for oblivious subspace embeddings

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