





















An oblivious subspace embedding (OSE), characterized by parameters $m,n,d,ε,δ$, is a random matrix $Π\in \mathbb{R}^{m\times n}$ such that for any $d$-dimensional subspace $T\subseteq \mathbb{R}^n$, $\Pr_Π[\forall x\in T, (1-ε)\|x\|_2 \leq \|Πx\|_2\leq (1+ε)\|x\|_2] \geq 1-δ$. For $ε$ and $δ$ at most a small constant, we show that any OSE with one nonzero entry in each column must satisfy that $m = Ω(d^2/(ε^2δ))$, establishing the optimality of the classical Count-Sketch matrix. When an OSE has $1/(9ε)$ nonzero entries in each column, we show it must hold that $m = Ω(ε^{O(δ)} d^2)$, improving on the previous $Ω(ε^2 d^2)$ lower bound due to Nelson and Nguyen (ICALP 2014).
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。