## Abstract

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.

Original language | English (US) |
---|---|

Title of host publication | ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |

Editors | Daniel Marx |

Publisher | Association for Computing Machinery |

Pages | 1279-1297 |

Number of pages | 19 |

ISBN (Electronic) | 9781611976465 |

State | Published - 2021 |

Externally published | Yes |

Event | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States Duration: Jan 10 2021 → Jan 13 2021 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Conference

Conference | 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 |
---|---|

Country/Territory | United States |

City | Alexandria, Virtual |

Period | 1/10/21 → 1/13/21 |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics