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

Abstract. We consider the task of certifying that a random [Formula: see text]-dimensional subspace [Formula: see text] in [Formula: see text] is well-spread—every vector [Formula: see text] satisfies [Formula: see text]. In a seminal work, Barak et al. [ Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 307–326] showed a polynomial-time certification algorithm when [Formula: see text]. On the other hand, when [Formula: see text], the certification task is information-theoretically possible but there is evidence that it is computationally hard [C. Mao and A. S. Wein, Optimal Spectral Recovery of a Planted Vector in a Subspace, preprint, arXiv:2105.15081, 2021; H. Chen and T. d’Orsi, Proc. Mach. Learn, Res, (PMLR), 178 (2022), pp. 1–31], a phenomenon known as the information-computation gap. In this paper, we give subexponential-time certification algorithms in the [Formula: see text] regime. Our algorithm runs in time [Formula: see text] when [Formula: see text], establishing a smooth tradeoff 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 tradeoff for this task.