We study the problem of robust subspace recovery (RSR) in the presence of adversarial outliers. That is, we seek a subspace that contains a large portion of a dataset when some fraction of the data points are arbitrarily corrupted. We first examine a theoretical estimator that is intractable to calculate and use it to derive information-theoretic bounds of exact recovery. We then propose two tractable estimators: a variant of RANSAC and a simple relaxation of the theoretical estimator. The two estimators are fast to compute and achieve state-of-the-art theoretical performance in a noiseless RSR setting with adversarial outliers. The former estimator achieves better theoretical guarantees in the noiseless case, while the latter estimator is robust to small noise, and its guarantees significantly improve with non-adversarial models of outliers. We give a complete comparison of guarantees for the adversarial RSR problem, as well as a short discussion on the estimation of affine subspaces.
Recent algorithms in the literature on adversarial robustness can also be used to learn subspaces @cite_21 . For example, the Robustly Learning a Gaussian (RLG) algorithm could be used to estimate an underlying low-rank covariance matrix up to @math error when there is an @math -percentage of outliers. However, this result requires the inlier data to be Gaussian. Another recent paper by @cite_57 uses resilience to approximate low-rank matrices in the presence of adversarial outliers. This method, which we call Resilience Recovery (RR), outputs a matrix of higher rank that can approximate a low-rank matrix. For both of these methods, exact recovery of a subspace is not possible.
@cite_57 @cite_21
2597655115 1539726260
We introduce a criterion, resilience, which allows properties of a dataset (such as its mean or best low rank approximation) to be robustly computed, even in the presence of a large fraction of arbitrary additional data. Resilience is a weaker condition than most other properties considered so far in the literature, and yet enables robust estimation in a broader variety of settings. We provide new information-theoretic results on robust distribution learning, robust estimation of stochastic block models, and robust mean estimation under bounded kth moments. We also provide new algorithmic results on robust distribution learning, as well as robust mean estimation in p-norms. Among our proof techniques is a method for pruning a high-dimensional distribution with bounded 1st moments to a stable "core" with bounded 2nd moments, which may be of independent interest. We describe ways to define and calculate L 1 -norm signal subspaces that are less sensitive to outlying data than L 2 -calculated subspaces. We start with the computation of the L 1 maximum-projection principal component of a data matrix containing N signal samples of dimension D. We show that while the general problem is formally NP-hard in asymptotically large N, D, the case of engineering interest of fixed dimension D and asymptotically large sample size N is not. In particular, for the case where the sample size is less than the fixed dimension , we present in explicit form an optimal algorithm of computational cost 2 N . For the case N ≥ D, we present an optimal algorithm of complexity O(N D ). We generalize to multiple L 1 -max-projection components and present an explicit optimal L 1 subspace calculation algorithm of complexity O(N DK-K+1 ) where K is the desired number of L 1 principal components (subspace rank). We conclude with illustrations of L 1 -subspace signal processing in the fields of data dimensionality reduction, direction-of-arrival estimation, and image conditioning restoration.