Nelson–Nguyen conjecture on sparse oblivious subspace embeddings
Fix a subspace dimension ddd and distortion parameters α=β∈(0,1)\alpha = \beta \in (0,1)α=β∈(0,1). A random sparse matrix Φ:Rn→Rk\bm{\Phi}: \mathbb{R}^n \to \mathbb{R}^kΦ:Rn→Rk has at most ζ\zetaζ nonzero entr…
MathDB