Robust computation of linear models by convex relaxation

Abstract

Consider a dataset of vector-valued observations that consists of noisy inliers, which are explained well by a low-dimensional subspace, along with some number of outliers. This work describes a convex optimization problem, called REAPER, that can reliably fit a low-dimensional model to this type of data. This approach parameterizes linear subspaces using orthogonal projectors, and it uses a relaxation of the set of orthogonal projectors to reach the convex formulation. The paper provides an efficient algorithm for solving the REAPER problem, and it documents numerical experiments which confirm that REAPER can dependably find linear structure in synthetic and natural data. In addition, when the inliers lie near a low-dimensional subspace, there is a rigorous theory that describes when REAPER can approximate this subspace.

Formerly titled "Robust computation of linear models, or How to find a needle in a haystack"

Cited by in corpus (19)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis
• An Overview of Robust Subspace Recovery
• Asymptotic performance of PCA for high-dimensional heteroscedastic data
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Innovation Pursuit: A New Approach to Subspace Clustering
• Identifying Outliers in Large Matrices via Randomized Adaptive Compressive Sampling
• Fast, Robust and Non-convex Subspace Recovery
• Anomaly Detection based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation
• Fair Principal Component Analysis and Filter Design
• Completing Low-Rank Matrices with Corrupted Samples from Few Coefficients in General Basis
• Subspace Clustering via Optimal Direction Search
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search
• Low Rank Matrix Recovery with Simultaneous Presence of Outliers and Sparse Corruption
• Exact Camera Location Recovery by Least Unsquared Deviations
• Robust PCA via Regularized REAPER with a Matrix-Free Proximal Algorithm
• Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning
• Distributed Robust Subspace Recovery
• Connective Reconstruction-based Novelty Detection