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

We consider the task of certifying that a random d-dimensional subspace X in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbb{R}^{\gamma}$</tex> is well-spread - every vec-tor <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\chi\in X$</tex> satisfies <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$c\sqrt{n}\Vert x\Vert_{2}\leq\Vert x\Vert_{1}\leq\sqrt{n}^{-}\Vert x\Vert_{2}$</tex>. In a seminal work, Barak et. al. [3] showed a polynomial-time certification algorithm when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d\leqslant O(\sqrt{n})$</tex>. On the other hand, when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d \gg \sqrt{n} r$</tex> the certification task is information-theoretically possible but there is evidence that it is computationally hard [10], [39], a phenomenon known as the information-computation gap. In this paper, we give sub exponential-time certification algorithms in the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$d \ll \sqrt{n}$</tex> regime. Our algorithm runs in time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\exp(\tilde{O}(n^{\varepsilon}))$</tex> when <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\dot{d} \leqslant \widetilde{O}\left(n^{\frac{1+\varepsilon}{2}}\right)$</tex>, 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.