Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold

Abstract

We consider the task of certifying that a random $d$-dimensional subspace $X$ in ${\mathbb{R}}^n$ is well-spread - every vector $x\in X$ satisfies $c\sqrt{n}\Vert x{\Vert }_2\le \Vert x{\Vert }_1\le \sqrt{n}\Vert x{\Vert }_2$. In a seminal work, Barak et. al. showed a polynomial-time certification algorithm when $d\le O(\sqrt{n})$. On the other hand, when $d\gg \sqrt{n}$, the certification task is information-theoretically possible but there is evidence that it is computationally hard [MW21,Cd22], a phenomenon known as the information-computation gap. In this paper, we give subexponential-time certification algorithms in the $d\gg \sqrt{n}$ regime. Our algorithm runs in time $\exp (\tilde{O}(n^{\epsilon }))$ when $d\le \tilde{O}(n^{(1+\epsilon )/2})$, establishing a smooth trade-off between runtime and the dimension. Our techniques naturally extend to the related planted problem, where the task is to recover a sparse vector planted in a random subspace. Our algorithm achieves the same runtime and dimension trade-off for this task.

32 pages, 2 Figures