Robust Computation of Linear Models by Convex Relaxation

Consider a data set 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 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 that 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.

• Publication year

  2012

• Venue

  Foundations of Computational Mathematics

• Publication date

  2012-02-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s10208-014-9221-0arXiv 1202.4044
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Approximation Algorithms

  2021cited by this paper
• Perturbation Analysis Of Optimization Problems

  2016cited by this paper
• lp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${l_p}$$\end{document}-Recovery of the Most Significant Subspace Amon

  2014cited by this paper
• Exact and Stable Recovery of Rotations for Robust Synchronization

  2012cited by this paper
• On the Sample Complexity of Robust PCA

  2012influential reference
• Robust Statistics, 2nd edn

  2011influential reference
• Robust recovery of multiple subspaces by geometric l_p minimization

  2011cited by this paper
• Improving the Thresholds of Sparse Recovery: An Analysis of a Two-Step Reweighted Basis Pursuit Algorithm

  2011cited by this paper
• A novel M-estimator for robust PCA

  2011influential reference
• Robust PCA via Outlier Pursuit

  2010cited by this paper
• Robust Recovery of Subspace Structures by Low-Rank Representation

  2010cited by this paper
• Efficient computation of robust low-rank matrix approximations in the presence of missing data using the L1 norm

  2010cited by this paper
• Two proposals for robust PCA using semidefinite programming

  2010influential reference
• Principal Component Analysis with Contaminated Data: The High Dimensional Case

  2010cited by this paper
• Rank-Sparsity Incoherence for Matrix Decomposition

  2009cited by this paper
• Median K-Flats for hybrid linear modeling with many outliers

  2009cited by this paper
• High dimensional Principal Component Analysis with contaminated data

  2009cited by this paper
• A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis.

  2009cited by this paper
• Robust PCA and clustering in noisy mixtures

  2009cited by this paper
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions

  2009cited by this paper
• Robust principal component analysis?

  2009influential reference
• Corrigendum in “Just Relax: Convex Programming Methods for Identifying Sparse Signals in Noise” [Mar 06 1030-1051]

  2009cited by this paper
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions

  2009cited by this paper
• Genes mirror geography within Europe

  2008cited by this paper
• Principal Component Analysis Based on L1-Norm Maximization

  2008cited by this paper
• Graph Implementations for Nonsmooth Convex Programs

  2008influential reference
• Efficient algorithms using the multiplicative weights update method

  2007cited by this paper
• Algorithms for Projection-Pursuit Robust Principal Component Analysis

  2007cited by this paper
• Enhancing Sparsity by Reweighted ℓ1 Minimization

  2007cited by this paper
• R1-PCA: rotational invariant L1-norm principal component analysis for robust subspace factorization

  2006cited by this paper
• Robust Statistics: Theory and Methods

  2006cited by this paper
• Just relax: convex programming methods for identifying sparse signals in noise

  2006cited by this paper
• Principal components analysis corrects for stratification in genome-wide association studies

  2006cited by this paper
• Acquiring linear subspaces for face recognition under variable lighting

  2005cited by this paper
• Robust Regression and Outlier Detection

  2005cited by this paper
• The elements of statistical learning: data mining, inference and prediction

  2005influential reference
• Principal Components and Orthogonal Regression Based on Robust Scales

  2005cited by this paper
• Clustering with Bregman Divergences

  2005cited by this paper
• Schur Complements and Matrix Inequalities: Operator-Theoretic Approach

  2005cited by this paper
• Learning Generative Visual Models from Few Training Examples: An Incremental Bayesian Approach Tested on 101 Object Categories

  2004cited by this paper
• A Framework for Robust Subspace Learning

  2003cited by this paper
• Clustering appearances of objects under varying illumination conditions

  2003cited by this paper
• On the Gauss-Newton method for l1 orthogonal distance regression

  2002cited by this paper
• Economic inequality and burden-sharing in the provision of local environmental quality

  2002cited by this paper
• The concentration of measure phenomenon

  2001cited by this paper
• Some problems in orthogonal distance and non-orthogonal distance regression

  2001cited by this paper
• Uncertainty principles and ideal atomic decomposition

  2001cited by this paper
• Robust principal component analysis for computer vision

  2001cited by this paper
• Chapter 8 - Local Operator Theory, Random Matrices and Banach Spaces

  2001cited by this paper
• Lambertian reflectance and linear subspaces

  2001cited by this paper
• Principal Component Analysis Based on Robust Estimators of the Covariance or Correlation Matrix: Influence Functions and Efficiencies

  2000cited by this paper
• On the Convergence of the Lagged Diffusivity Fixed Point Method in Total Variation Image Restoration

  1999cited by this paper
• Robust principal component analysis for functional data

  1999cited by this paper
• A Multibody Factorization Method for Independently Moving Objects

  1998cited by this paper
• Numerical Methods for Least Squares Problems

  1996cited by this paper
• Robust principal component analysis by self-organizing rules based on statistical physics approach

  1995cited by this paper
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

  1995cited by this paper
• 5/spl plusmn/2 eigenimages suffice: an empirical investigation of low-dimensional lighting models

  1995cited by this paper
• Robust Singular Value Decompositions: A New Approach to Projection Pursuit

  1993cited by this paper
• Orthogonal linear regression algorithm based on augmented matrix formulation

  1993cited by this paper
• On the Sum of the Largest Eigenvalues of a Symmetric Matrix

  1992cited by this paper
• Cones of Matrices and Set-Functions and 0-1 Optimization

  1991cited by this paper
• Probability in Banach Spaces: Isoperimetry and Processes

  1991cited by this paper
• Total least squares problem - computational aspects and analysis

  1991cited by this paper
• An iterative linear programming solution to the Euclidean regression model

  1991cited by this paper
• Least orthogonal absolute deviations

  1988cited by this paper
• Improving information retrieval using latent semantic indexing

  1988cited by this paper
• An introduction to L 1 -norm based statistical data analysis

  1987cited by this paper
• Asymptotic behaviour of S-estimates of multivariate location parameters and dispersion matrices

  1987cited by this paper
• An Analysis of the Total Approximation Problem in Separable Norms, and an Algorithm for the Total $l_1 $ Problem

  1985cited by this paper
• Projection-Pursuit Approach to Robust Dispersion Matrices and Principal Components: Primary Theory and Monte Carlo

  1985cited by this paper
• Least Median of Squares Regression

  1984cited by this paper
• Some extensions of W. Gautschi’s inequalities for the gamma function

  1983cited by this paper
• Residuals and Influence in Regression

  1982cited by this paper
• Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography

  1981cited by this paper
• Robust Estimation of Dispersion Matrices and Principal Components

  1981cited by this paper
• Linear convergence of generalized Weiszfeld's method

  1980cited by this paper
• Probability on Banach spaces

  1978cited by this paper
• Robust $M$-Estimators of Multivariate Location and Scatter

  1976cited by this paper
• The Method of Least Squares and Some Alternatives: Part III

  1975cited by this paper
• How to Find a Needle in a Haystack

  1973cited by this paper
• The Method of Least Squares and Some Alternatives.

  1972cited by this paper
• A principal axis transformation for non-hermitian matrices

  1939cited by this paper

• Dual-RSRAE: Enhancing ship inspection operations through dual robust subspace recovery auto-encoder in port state control

  2026cites this paper
• T-Rex: Fitting a Robust Factor Model via Expectation-Maximization

  2025cites this paper
• A Flag Decomposition for Hierarchical Datasets

  2025cites this paper
• Nested subspace learning with flags

  2025cites this paper
• Cycle-Sync: Robust Global Camera Pose Estimation through Enhanced Cycle-Consistent Synchronization

  2025cites this paper
• Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing

  2025cites this paper
• A Subspace-Constrained Tyler's Estimator and its Applications to Structure from Motion *

  2024influential citation
• Theoretical Guarantees for the Subspace-Constrained Tyler's Estimator

  2024influential citation
• Beyond the Known: Adversarial Autoencoders in Novelty Detection

  2024influential citation
• CVAD-GAN: Constrained video anomaly detection via generative adversarial network

  2024cites this paper
• HARD: Hyperplane ARrangement Descent

  2024cites this paper
• A Riemannian Alternating Direction Method of Multipliers

  2024cites this paper
• Multi-modal data novelty detection with adversarial autoencoders

  2024cites this paper
• Nonlinear Eigen-approach ADMM for Sparse Optimization on Stiefel Manifold

  2024influential citation
• Nonsmooth Optimization over the Stiefel Manifold and Beyond: Proximal Gradient Method and Recent Variants

  2024cites this paper
• Efficient Convex Optimization for Non-convex Non-smooth Image Restoration

  2024cites this paper
• Block Coordinate Descent on Smooth Manifolds: Convergence Theory and Twenty-One Examples

  2023cites this paper
• Consensus-Based Optimization with Truncated Noise

  2023cites this paper
• Complex Background Reconstruction for Novelty Detection

  2023cites this paper
• On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation

  2023cites this paper
• The Ideal Continual Learner: An Agent That Never Forgets

  2023cites this paper
• A Robust Likelihood Model for Novelty Detection

  2023cites this paper
• Learning Representations for Novelty and Anomaly Detection

  2023cites this paper
• ARCS: Accurate Rotation and Correspondence Search

  2022influential citation
• A Riemannian ADMM

  2022cites this paper
• Connective Reconstruction-Based Novelty Detection

  2022cites this paper
• Theoretical Analysis of Null Foley-Sammon Transform and its Implications

  2022cites this paper
• Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression

  2022cites this paper
• Generative Probabilistic Novelty Detection with Isometric Adversarial Autoencoders

  2022cites this paper
• Clustering a union of linear subspaces via matrix factorization and innovation search

  2022cites this paper
• Stabilizing Adversarially Learned One-Class Novelty Detection Using Pseudo Anomalies

  2022cites this paper
• Stochastic and Private Nonconvex Outlier-Robust PCA

  2022influential citation
• Differentiable Unsupervised Feature Selection

  2022cites this paper
• Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension

  2022cites this paper
• Provable Clustering of a Union of Linear Manifolds Using Optimal Directions

  2022cites this paper
• Manifold Alignment Aware Ants: A Markovian Process for Manifold Extraction

  2022cites this paper
• Anisotropic Diffusion in Consensus-Based Optimization on the Sphere

  2021cites this paper
• Majorization-Minimization on the Stiefel Manifold With Application to Robust Sparse PCA

  2021cites this paper
• Applications of Generative Adversarial Networks in Anomaly Detection: A Systematic Literature Review

  2021cites this paper
• Probabilistic Robust Autoencoders for Outlier Detection

  2021cites this paper
• Probabilistic Robust Autoencoders for Anomaly Detection

  2021cites this paper
• Efficient Deterministic Search With Robust Loss Functions for Geometric Model Fitting

  2021cites this paper
• Provable Data Clustering via Innovation Search

  2021cites this paper
• Dual Principal Component Pursuit for Robust Subspace Learning: Theory and Algorithms for a Holistic Approach

  2021influential citation
• Closed-Form, Provable, and Robust PCA via Leverage Statistics and Innovation Search

  2021cites this paper
• Dual Principal Component Pursuit for Learning a Union of Hyperplanes: Theory and Algorithms

  2021influential citation
• G2D: Generate to Detect Anomalies

  2020cites this paper
• Multi-head enhanced self-attention network for novelty detection

  2020cites this paper
• Robust Variational Autoencoding with Wasserstein Penalty for Novelty Detection

  2020cites this paper
• Robust PCA via Regularized Reaper with a Matrix-Free Proximal Algorithm

  2020cites this paper
• Inertial Stochastic PALM and its Application for Learning Student-t Mixture Models

  2020cites this paper
• Fuzzy Space Partitioning Based on Hyperplanes Defined by Eigenvectors for Takagi-Sugeno Fuzzy Model Identification

  2020cites this paper
• Old Is Gold: Redefining the Adversarially Learned One-Class Classifier Training Paradigm

  2020cites this paper
• Deep End-to-End One-Class Classifier

  2020cites this paper
• Consensus-based Optimization on the Sphere II: Convergence to Global Minimizers and Machine Learning

  2020cites this paper
• Fair Principal Component Analysis and Filter Design

  2020cites this paper
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications

  2020cites this paper
• On the rotational invariant L1-norm PCA

  2020cites this paper
• The Application and Problem Analysis of Computer Technology in English Information Processing

  2020cites this paper
• Geometric Estimation via Robust Subspace Recovery

  2020cites this paper
• Anomaly Detection Based on Zero-Shot Outlier Synthesis and Hierarchical Feature Distillation

  2020cites this paper
• Rethink Autoencoders: Robust Manifold Learning

  2020cites this paper
• Modal Principal Component Analysis

  2020cites this paper
• Novelty Detection via Robust Variational Autoencoding

  2020cites this paper
• G2D: Generate to Detect Anomaly

  2020cites this paper
• Continuous Iteratively Reweighted Least Squares Algorithm for Solving Linear Models by Convex Relaxation

  2019influential citation
• Learning Competitive and Discriminative Reconstructions for Anomaly Detection

  2019cites this paper
• Robust Subspace Recovery Layer for Unsupervised Anomaly Detection

  2019cites this paper
• Robust Subspace Recovery with Adversarial Outliers

  2019influential citation
• On the Rotational Invariant $L_1$-Norm PCA

  2019cites this paper
• On the Robust PCA and Weiszfeld’s Algorithm

  2019cites this paper
• Noisy Dual Principal Component Pursuit

  2019influential citation
• A Novel and Efficient CVAE-GAN-Based Approach With Informative Manifold for Semi-Supervised Anomaly Detection

  2019cites this paper
• Binary component decomposition Part II: The asymmetric case

  2019influential citation
• Outlier Detection and Robust PCA Using a Convex Measure of Innovation

  2019cites this paper
• A Linearly Convergent Method for Non-Smooth Non-Convex Optimization on the Grassmannian with Applications to Robust Subspace and Dictionary Learning

  2019cites this paper
• Nonsmooth Optimization over Stiefel Manifold: Riemannian Subgradient Methods

  2019cites this paper
• Manifold Proximal Point Algorithms for Dual Principal Component Pursuit and Orthogonal Dictionary Learning

  2019cites this paper
• Robust Group Synchronization via Cycle-Edge Message Passing

  2019cites this paper
• Outlier Detection and Data Clustering via Innovation Search

  2019cites this paper
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods

  2019influential citation
• Unsupervised Novelty Detection in Video with Adversarial Autoencoder Based on Non-Euclidean Space

  2019cites this paper
• Robust Estimators in High-Dimensions Without the Computational Intractability

  2019cites this paper
• Semi-supervised Anomaly Detection Using GANs for Visual Inspection in Noisy Training Data

  2018cites this paper
• Adversarially Learned One-Class Classifier for Novelty Detection

  2018cites this paper
• Sparse Methods for Learning Multiple Subspaces from Large-scale, Corrupted and Imbalanced Data

  2018cites this paper
• Anomaly Detection Using GANs for Visual Inspection in Noisy Training Data

  2018cites this paper
• Reconstruction : Label “ 7 ”-inlier Label “ 0 ”-outlier Input : Reconstruction : Figure 2

  2018cites this paper
• Image Segmentation Using Subspace Representation and Sparse Decomposition

  2018cites this paper
• Improving <inline-formula><tex-math notation="LaTeX">$K$</tex-math></inline-formula>-Subspaces via Coherence Pursuit

  2018cites this paper
• Dual Principal Component Pursuit: Probability Analysis and Efficient Algorithms

  2018influential citation
• Dual Principal Component Pursuit: Improved Analysis and Efficient Algorithms

  2018influential citation
• Streaming Principal Component Analysis in Noisy Settings

  2018influential citation
• Principled approaches to robust machine learning and beyond

  2018cites this paper
• Generative Probabilistic Novelty Detection with Adversarial Autoencoders

  2018cites this paper
• Robust PCA , Subspace Learning , and Tracking *

  2018cites this paper
• An Overview of Robust Subspace Recovery

  2018influential citation
• Distributed Robust Subspace Recovery

  2017influential citation
• Subspace Clustering via Optimal Direction Search

  2017cites this paper
• Asymptotic performance of PCA for high-dimensional heteroscedastic data

  2017cites this paper