论文标题
绘制操作员规范，沙滕规范和子空间嵌入的紧密界限
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings
论文作者
论文摘要
我们考虑以下遗漏的草图问题：给定（0,1/3）$和$ n \ geq d/ε^2 $，设计$ \ Mathcal {d} $上的$ \ Mathbb {r}^{r}^{k \ times nd} $ f：\ mathbb {r} \ rightarrow \ mathbb {r} $，因此，对于任何$ n \ times d $ d $ a $ a $，$$ \ pr_ {s \ sim \ sim \ mathcal {d}} [（1-ε）\ | a \ | a \ | _ {op} {op} \ geq 2/3，$$其中$ \ | a \ | _ {op} $是$ a $ a $ and $ s（a）$的运算符标准，表示$ s \ cdot a $，将$ a $解释为$ \ mathbb {r}^{r}^{nd} $的矢量。对于此问题，我们显示了$ k =ω（d^2/ε^2）$的紧密下限。我们的结果大大加强了尼尔森和nguyen的结果（ICALP，2014年），因为它（1）仅适用于估计运算符规范，可以估算给定任何OSE，并且（2）适用于一般线性运算符$ s $ $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ s $ s $ s $ s $ s $ s（a）$ s（a）$ sepriact lineal costriact costriact fortriact fortriact fortriact fortriact fortriact of lineal fluciact。我们的技术还意味着通过常规线性草图近似于整数$ p $的第一个紧密界限，从$ k =ω（n^{2-6/p}）$ [regev，2014]提高了先前的下界，至$ k =ω（n^{2-4/p}）$。重要的是，要勾勒出运营商规范的$α$，其中$α-1 =ω（1）$，我们获得了一个紧密的$ k =ω（n^2/α^4）$绑定，与Andoni和Nguyen的上限匹配（Soda，2013），并改善了前面的$ K =ω（N^2/α^6^6）$ wister。最后，我们还获得了近似KY风扇规范的第一界限。
We consider the following oblivious sketching problem: given $ε\in (0,1/3)$ and $n \geq d/ε^2$, design a distribution $\mathcal{D}$ over $\mathbb{R}^{k \times nd}$ and a function $f: \mathbb{R}^k \times \mathbb{R}^{nd} \rightarrow \mathbb{R}$, so that for any $n \times d$ matrix $A$, $$\Pr_{S \sim \mathcal{D}} [(1-ε) \|A\|_{op} \leq f(S(A),S) \leq (1+ε)\|A\|_{op}] \geq 2/3,$$ where $\|A\|_{op}$ is the operator norm of $A$ and $S(A)$ denotes $S \cdot A$, interpreting $A$ as a vector in $\mathbb{R}^{nd}$. We show a tight lower bound of $k = Ω(d^2/ε^2)$ for this problem. Our result considerably strengthens the result of Nelson and Nguyen (ICALP, 2014), as it (1) applies only to estimating the operator norm, which can be estimated given any OSE, and (2) applies to distributions over general linear operators $S$ which treat $A$ as a vector and compute $S(A)$, rather than the restricted class of linear operators corresponding to matrix multiplication. Our technique also implies the first tight bounds for approximating the Schatten $p$-norm for even integers $p$ via general linear sketches, improving the previous lower bound from $k = Ω(n^{2-6/p})$ [Regev, 2014] to $k = Ω(n^{2-4/p})$. Importantly, for sketching the operator norm up to a factor of $α$, where $α- 1 = Ω(1)$, we obtain a tight $k = Ω(n^2/α^4)$ bound, matching the upper bound of Andoni and Nguyen (SODA, 2013), and improving the previous $k = Ω(n^2/α^6)$ lower bound. Finally, we also obtain the first lower bounds for approximating Ky Fan norms.
