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 $lpha$ 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(rac{1}{lpha})$ 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.
展开▼
机译：在异常值的存在中，从数据中学习是统计数据的根本问题。在这项工作中，我们在存在压倒性统计数据的基本问题的存在下，研究了子空间恢复的根本问题。鉴于DataSet在$ D $维度的未知$ k $维子空间中均匀分发$ alpha $ fillact（不到一半），并且在剩余数据上没有额外的假设，目标是恢复一个简洁的$ o（ frac {1} { alpha}）$子空间列表，其中一个与种植子空间不相关。我们为“列出可解码子空间恢复”问题提供了第一多项式时间算法，并在更常规的列表中对其进行分布，该分布是“证明弹性”的捕获状态的发布，该列出可解码的平均估计和回归。
展开▼
