List-decodable subspace recovery: Dimension independent error in polynomial time

In list-decodable subspace recovery, the input is a collection of n points αn (for some α ≪ 1/2) of which are drawn i.i.d. from a distribution D with a isotropic rank r covariance Π_∗ (the inliers) and the rest are arbitrary, potential adversarial outliers. The goal is to recover a O(1/α) size list of candidate covariances that contains a Π^ close to Π_∗. Two recent independent works [56, 3] gave algorithms for this problem that work whenever D satisfies an algorithmic variant of anti-concentration condition (certifiable anticoncentration). The running time of both these algorithms, however, is d^Ω(1/α4) and the error bounds on kΠ − Π_∗k_F grow with r (polynomially in r in [56] and logarithmically in [3]) that can be as large as Ω(d). In this work, we improve on these results on all three fronts: we obtain dimension-independent error in fixed-polynomial running time under less restrictive distributional assumptions. Specifically, we give a poly(1/α)d^O(1) time algorithm that outputs a list containing a Π^ satisfying ||||||Π^ − Π_{∗ ||||||F} ≤ O(1/α). Our result only needs certifiable hypercontractivity of degree 2 polynomials -a condition satisfied by a much broader family of distributions in contrast to certifiable anticoncentration. As a result, in addition to Gaussians, our algorithm applies to uniform distribution on the hypercube and q-ary cubes and arbitrary product distributions with subgaussian marginals. Prior work [56] had identified such distributions as potential hard examples as such distributions do not exhibit strong enough anti-concentration. When D satisfies certifiable anti-concentration, we obtain a stronger error guarantee of ||||||Π^ − Π_{∗ ||||||F} ≤ η for any arbitrary η > 0 in d^O(poly(1/α)+log(1/η⁾⁾ time. The proof of the first result uses certifiable hypercontractivity of degree 2 polynomials to give a low-degree sum-of-squares proof of identifiability of the low dimensional structure in the presence of overwhelming fraction of outliers in input data. Our second result relies on a novel bootstrapping of the guarantees from the first with a new exponential error reduction mechanism within SoS along with certifiable anti-concentration.