Robust computation of linear models by convex relaxation
Preprint
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.Keywords
All Related Versions
This publication has 52 references indexed in Scilit:
- ${l_p}$ l p -Recovery of the Most Significant Subspace Among Multiple Subspaces with OutliersConstructive Approximation, 2014
- A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysisBiostatistics, 2009
- Genes mirror geography within EuropeNature, 2008
- Algorithms for Projection–Pursuit robust principal component analysisChemometrics and Intelligent Laboratory Systems, 2007
- Principal components analysis corrects for stratification in genome-wide association studiesNature Genetics, 2006
- Principal component analysis based on robust estimators of the covariance or correlation matrix: influence functions and efficienciesBiometrika, 2000
- A Multibody Factorization Method for Independently Moving ObjectsInternational Journal of Computer Vision, 1998
- Least orthogonal absolute deviationsComputational Statistics & Data Analysis, 1988
- Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography1987
- A principal axis transformation for non-hermitian matricesBulletin of the American Mathematical Society, 1939