论文标题
认证限制等轴测属性的平均情况时间复杂性
The Average-Case Time Complexity of Certifying the Restricted Isometry Property
论文作者
论文摘要
在压缩感应中，$ m \ times n $传感矩阵（其中$ m <n $）上的限制等轴测属性（RIP）保证了稀疏向量的有效重建。矩阵具有$（s，δ）$ - $ \ mathsf {rip} $属性，如果在$ s $ s $ -s-sparse vectors上表现为$δ$ - approximate等轴测图。众所周知，具有I.I.D的$ M \ times n $矩阵$ \ MATHCAL {N}（0,1/m）$条目为$（s，δ）$ - $ \ MATHSF {RIP} $，只要$ s \sellysimΔ^2 m/\ log n $，概率很高。另一方面，旨在确定构建$（s，δ）$ - $ \ mathsf {rip} $矩阵时的大多数先前的作品在$ s \ gg \ sqrt {m} $时都失败了。找到RIP矩阵的另一种方法可能是绘制随机的高斯矩阵并证明它确实是RIP。但是，有证据表明，在最坏情况和平均情况下，当$ s \ gg \ sqrt {m} $时，此认证任务在计算上很难计算。 在本文中，我们研究了与I.I.D. $ M \ times n $矩阵认证的确切平均时间复杂性。 $ \ MATHCAL {N}（0,1/M）$条目，在“可能但难”的制度$ \ sqrt {M} \ ll S \ lysesim m/\ log n $中。基于对低度似然比的分析，我们提供了严格的证据表明，需要次指数运行时$ n^{\tildeΩ（s^2/m）} $，证明最大耐受性稀疏性和所需的计算能力之间的平稳权衡。该下限本质上是紧密的，与Koiran和Zouzias引起的现有算法的运行时间相匹配。我们的硬度结果允许$δ$在$（0,1）$中获得任何恒定值，从而捕获了压缩感应的相关制度。这改善了Wang，Berthet和Plan的现有平均值硬度结果，该结果仅限于$δ= O（1）$。
In compressed sensing, the restricted isometry property (RIP) on $M \times N$ sensing matrices (where $M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the $(s,δ)$-$\mathsf{RIP}$ property if behaves as a $δ$-approximate isometry on $s$-sparse vectors. It is well known that an $M\times N$ matrix with i.i.d. $\mathcal{N}(0,1/M)$ entries is $(s,δ)$-$\mathsf{RIP}$ with high probability as long as $s\lesssim δ^2 M/\log N$. On the other hand, most prior works aiming to deterministically construct $(s,δ)$-$\mathsf{RIP}$ matrices have failed when $s \gg \sqrt{M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when $s \gg \sqrt{M}$, both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for $M\times N$ matrices with i.i.d. $\mathcal{N}(0,1/M)$ entries, in the "possible but hard" regime $\sqrt{M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime $N^{\tildeΩ(s^2/M)}$ is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows $δ$ to take any constant value in $(0,1)$, which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wang, Berthet, and Plan, which is limited to $δ= o(1)$.
