List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time

In list-decodable subspace recovery, the input is a collection of $n$ points $\alpha n$ (for some $\alpha \ll 1/2$) of which are drawn i.i.d. from a distribution $\mathcal{D}$ with a isotropic rank $r$ covariance $\Pi_*$ (the \emph{inliers}) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a $O(1/\alpha)$ size list of candidate covariances that contains a $\hat{\Pi}$ close to $\Pi_*$. Two recent independent works (Raghavendra-Yau, Bakshi-Kothari 2020) gave the first efficient algorithm for this problem. These results, however, obtain an error that grows with the dimension (linearly in [RY] and logarithmically in BK) at the cost of quasi-polynomial running time) and rely on \emph{certifiable anti-concentration} - a relatively strict condition satisfied essentially only by the Gaussian distribution. In this work, we improve on these results on all three fronts: \emph{dimension-independent} error via a faster fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a $poly(1/\alpha) d^{O(1)}$ time algorithm that outputs a list containing a $\hat{\Pi}$ satisfying $\|\hat{\Pi} -\Pi_*\|_F \leq O(1/\alpha)$. Our result only needs $\mathcal{D}$ to have \emph{certifiably hypercontractive} degree 2 polynomials. As a result, in addition to Gaussians, our algorithm applies to the uniform distribution on the hypercube and $q$-ary cubes and arbitrary product distributions with subgaussian marginals. Prior work (Raghavendra and Yau, 2020) had identified such distributions as potential hard examples as such distributions do not exhibit strong enough anti-concentration. When $\mathcal{D}$ satisfies certifiable anti-concentration, we obtain a stronger error guarantee of $\|\hat{\Pi}-\Pi_*\|_F \leq \eta$ for any arbitrary $\eta > 0$ in $d^{O(poly(1/\alpha) + \log (1/\eta))}$ time.
Comment: To appear in SODA 2021. This version fixes an issue in a technical claim bounding the variance of degree 2 polynomials and improves exposition