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 and the error bounds on ‖Π – Π∗‖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/α)dO(1) time algorithm that outputs a list containing a satisfying . 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 for any arbitrary η > 0 in dO(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. 1