论文标题
稀疏和$ \ ell_p $ - 限制的等轴测图
Sparsity and $\ell_p$-Restricted Isometry
论文作者
论文摘要
据说一个矩阵$ a $具有$ \ ell_p $限制的等轴测属性（$ \ ell_p $ -rip），如果对于所有矢量，$ x $ of某些稀疏$ k $，$ \ | {ax ax} \ | _p $大致与$ \ \ \ | {x}} \ | _p $大致相比。我们以$ m \ times n $等级的矩阵为$ n $和$ k =θ（n）$的等级矩阵研究此属性。在此参数制度中，$ \ ell_p $ -RIP矩阵与欧几里得部分紧密连接，并且是用于本地可测试代码的测试矩阵的“真实类似物”。 It is known that with high probability, random dense $m\times n$ matrices (e.g., with i.i.d. $\pm 1$ entries) are $\ell_2$-RIP with $k \approx m/\log n$, and sparse random matrices are $\ell_p$-RIP for $p \in [1,2)$ when $k, m = Θ(n)$.但是，当$ m =θ（n）$时，稀疏的随机矩阵已知不是$ \ ell_2 $ -rip，概率很高。 在此背景下，我们表明稀疏矩阵不能在我们的参数制度中$ \ ell_2 $ -rip。另一方面，对于$ p \ neq 2 $，我们表明每个$ \ ell_p $ -rip矩阵都必须稀疏。因此，稀疏性与$ \ ell_2 $ -rip不相容，但对于$ \ ell_p $ -rip而言，$ p \ neq 2 $都必须进行。 在适当的解释下，我们的负面结果约为$ \ ell_2 $ -rip，对于“ $ c^3 $ -LTCS”的一定连续类似物给出了不可能的结果：在最近的突破中构建的稳定速率，恒定距离和恒定位置的本地测试代码。
A matrix $A$ is said to have the $\ell_p$-Restricted Isometry Property ($\ell_p$-RIP) if for all vectors $x$ of up to some sparsity $k$, $\|{Ax}\|_p$ is roughly proportional to $\|{x}\|_p$. We study this property for $m \times n$ matrices of rank proportional to $n$ and $k = Θ(n)$. In this parameter regime, $\ell_p$-RIP matrices are closely connected to Euclidean sections, and are "real analogs" of testing matrices for locally testable codes. It is known that with high probability, random dense $m\times n$ matrices (e.g., with i.i.d. $\pm 1$ entries) are $\ell_2$-RIP with $k \approx m/\log n$, and sparse random matrices are $\ell_p$-RIP for $p \in [1,2)$ when $k, m = Θ(n)$. However, when $m = Θ(n)$, sparse random matrices are known to not be $\ell_2$-RIP with high probability. Against this backdrop, we show that sparse matrices cannot be $\ell_2$-RIP in our parameter regime. On the other hand, for $p \neq 2$, we show that every $\ell_p$-RIP matrix must be sparse. Thus, sparsity is incompatible with $\ell_2$-RIP, but necessary for $\ell_p$-RIP for $p \neq 2$. Under a suitable interpretation, our negative result about $\ell_2$-RIP gives an impossibility result for a certain continuous analog of "$c^3$-LTCs": locally testable codes of constant rate, constant distance and constant locality that were constructed in recent breakthroughs.
