论文标题
列表可解码子空间恢复
List Decodable Subspace Recovery
论文作者
论文摘要
在异常值的存在下从数据中学习是统计中的一个基本问题。在这项工作中，我们在存在压倒性异常值的基本问题的情况下，研究了强大的统计数据。 Given a dataset where an $α$ fraction (less than half) of the data is distributed uniformly in an unknown $k$ dimensional subspace in $d$ dimensions, and with no additional assumptions on the remaining data, the goal is to recover a succinct list of $O(\frac{1}α)$ subspaces one of which is nontrivially correlated with the planted subspace.我们为“可解码子空间恢复”问题提供了第一个多项式时间算法，并将其集成在更通用的列表框架下，以解码为“证实有弹性”的分布，这些分布捕获了可解码的平均值估计和回归列表的最先进状态。
Learning from data in the presence of outliers is a fundamental problem in statistics. In this work, we study robust statistics in the presence of overwhelming outliers for the fundamental problem of subspace recovery. Given a dataset where an $α$ fraction (less than half) of the data is distributed uniformly in an unknown $k$ dimensional subspace in $d$ dimensions, and with no additional assumptions on the remaining data, the goal is to recover a succinct list of $O(\frac{1}α)$ subspaces one of which is nontrivially correlated with the planted subspace. We provide the first polynomial time algorithm for the 'list decodable subspace recovery' problem, and subsume it under a more general framework of list decoding over distributions that are "certifiably resilient" capturing state of the art results for list decodable mean estimation and regression.
