Robust computation of linear models by convex relaxation
From MaRDI portal
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.
Recommendations
Cites work
- l_p-recovery of the most significant subspace among multiple subspaces with outliers
- A framework for robust subspace learning
- A penalized matrix decomposition, with applications to sparse principal components and canonical correlation analysis
- A principal axis transformation for non-hermitian matrices
- An Analysis of the Total Approximation Problem in Separable Norms, and an Algorithm for the Total l₁ Problem
- An iterative linear programming solution to the Euclidean regression model
- Asymptotic behaviour of S-estimates of multivariate location parameters and dispersion matrices
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Convex Analysis
- Corrigendum in “Just Relax: Convex Programming Methods for Identifying Sparse Signals in Noise” [Mar 06 1030-1051]
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Exact and stable recovery of rotations for robust synchronization
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Graph implementations for nonsmooth convex programs
- scientific article; zbMATH DE number 3899977 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 51511 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- scientific article; zbMATH DE number 194744 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Just relax: convex programming methods for identifying sparse signals in noise
- Least Median of Squares Regression
- Least orthogonal absolute deviations
- Linear convergence of generalized Weiszfeld's method
- Local operator theory, random matrices and Banach spaces.
- On orthogonal linear \(\ell_1\) approximation
- On the Convergence of the Lagged Diffusivity Fixed Point Method in Total Variation Image Restoration
- On the Gauss-Newton method for l1 orthogonal distance regression
- On the small balls problem for equivalent Gaussian measures
- On the Sum of the Largest Eigenvalues of a Symmetric Matrix
- Online Algorithms
- Orthogonal linear regression algorithm based on augmented matrix formulation
- Principal component analysis based on robust estimators of the covariance or correlation matrix: influence functions and efficiencies
- Principal component analysis.
- Projection-Pursuit Approach to Robust Dispersion Matrices and Principal Components: Primary Theory and Monte Carlo
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust computation of linear models by convex relaxation
- Robust Estimation of Dispersion Matrices and Principal Components
- Robust m-estimators of multivariate location and scatter
- Robust PCA and clustering in noisy mixtures
- Robust PCA via Outlier Pursuit
- Robust principal component analysis for functional data. (With comments)
- Robust principal component analysis?
- Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
- Robust Singular Value Decompositions: A New Approach to Projection Pursuit
- Robust Statistics
- Robust Statistics
- Some Extensions of W. Gautschi's Inequalities for the Gamma Function
- The Method of Least Squares and Some Alternatives: Part I
- The Method of Least Squares and Some Alternatives: Part II
- Two proposals for robust PCA using semidefinite programming
Cited in
(31)- Asymptotic performance of PCA for high-dimensional heteroscedastic data
- Tractable algorithms for robust model estimation
- On the robust PCA and Weiszfeld's algorithm
- Robust PCA via regularized \textsc{Reaper} with a matrix-free proximal algorithm
- Robust group synchronization via cycle-edge message passing
- On the rotational invariant \(L_1\)-norm PCA
- Robust computation of linear models by convex relaxation
- A novel M-estimator for robust PCA
- Robust _1 approaches to computing the geometric median and principal and independent components
- Stable camera motion estimation using convex programming
- Modal principal component analysis
- Dual principal component pursuit
- Robust subspace recovery by Tyler's M-estimator
- A well-tempered landscape for non-convex robust subspace recovery
- Robust estimators in high-dimensions without the computational intractability
- Distributed Robust Subspace Recovery
- Subspace clustering through sub-clusters
- Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
- scientific article; zbMATH DE number 7626752 (Why is no real title available?)
- Anisotropic diffusion in consensus-based optimization on the sphere
- Computational and statistical tradeoffs via convex relaxation
- Exact camera location recovery by least unsquared deviations
- Fast, robust and non-convex subspace recovery
- A convex program for mixed linear regression with a recovery guarantee for well-separated data
- Robust iterative fitting of multilinear models
- Robust Subspace Discovery via Relaxed Rank Minimization
- Relations among some low-rank subspace recovery models
- Efficient Convex Optimization for Non-convex Non-smooth Image Restoration
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
- Fast subspace approximation via greedy least-squares
- Relaxation analysis in a data driven problem with a single outlier
This page was built for publication: Robust computation of linear models by convex relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2351804)
