论文标题
疏忽子空嵌入的稀疏维度折衷
Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
论文作者
论文摘要
以参数为特征$ m，n，d，ε，δ$的遗忘子空间嵌入（OSE）是一个随机矩阵$π\ in \ mathbb {r}^{m \ times n} $ x \ in t，（1-ε）\ | x \ | _2 \ leq \ |πx\ | _2 \ leq（1+ε）\ | x \ | _2] \ geq1-Δ$。当OSE在每列中具有$ s \ le 1/2.001ε$ nonzero条目时，我们表明必须认为$ M =ω\ left（d^2/（d^2/（ε^2s^{1+o（δ）}）\ right）$，这是先前的第一个下部下限，以改进$ d^2 $和$ 1/ε$的乘法因子。 $ω\ left（d^2/s^{o（δ）} \ right）$下限由于li和liu（pods 2022）。当OSE具有$ s =ω（\ log（1/ε）/ε）$ nonzero条目中的条目时，我们表明必须认为，$ M =ω\ left（（（d/ε）^{1+1+1+1/4.001εs}/s}/s^{o（δ）} \ right是$ d $ d $ d $ d $ d $ d $ d $ d， $ω\ left（d^{1+1/（16εs+4）} \ right）$下限，尼尔森和nguyen（ICALP 2014）。第二个结果是在$ d，ε，s，δ$和$ m $中进行更一般权衡的特殊情况。
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-δ$. When an OSE has $s\le 1/2.001ε$ nonzero entries in each column, we show it must hold that $m = Ω\left(d^2/( ε^2s^{1+O(δ)})\right)$, which is the first lower bound with multiplicative factors of $d^2$ and $1/ε$, improving on the previous $Ω\left(d^2/s^{O(δ)}\right)$ lower bound due to Li and Liu (PODS 2022). When an OSE has $s=Ω(\log(1/ε)/ε)$ nonzero entries in each column, we show it must hold that $m = Ω\left((d/ε)^{1+1/4.001εs}/s^{O(δ)}\right)$, which is the first lower bound with multiplicative factors of $d$ and $1/ε$, improving on the previous $Ω\left(d^{1+1/(16εs+4)}\right)$ lower bound due to Nelson and Nguyen (ICALP 2014). This second result is a special case of a more general trade-off among $d,ε,s,δ$ and $m$.
