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
- 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?)
- 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_1 $ 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
- 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 Sum of the Largest Eigenvalues of a Symmetric Matrix
- On the small balls problem for equivalent Gaussian measures
- 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 Estimation of Dispersion Matrices and Principal Components
- Robust PCA and clustering in noisy mixtures
- Robust PCA via Outlier Pursuit
- Robust Singular Value Decompositions: A New Approach to Projection Pursuit
- Robust Statistics
- Robust Statistics
- Robust computation of linear models by convex relaxation
- Robust m-estimators of multivariate location and scatter
- Robust principal component analysis for functional data. (With comments)
- Robust principal component analysis?
- Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
- 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
- \(l_p\)-recovery of the most significant subspace among multiple subspaces with outliers
Cited in
(31)- Exact camera location recovery by least unsquared deviations
- On the robust PCA and Weiszfeld's algorithm
- Robust group synchronization via cycle-edge message passing
- On the rotational invariant \(L_1\)-norm PCA
- scientific article; zbMATH DE number 7626752 (Why is no real title available?)
- A novel M-estimator for robust PCA
- Robust subspace recovery by Tyler's M-estimator
- Robust estimators in high-dimensions without the computational intractability
- Relations among some low-rank subspace recovery models
- Robust _1 approaches to computing the geometric median and principal and independent components
- Robust Subspace Discovery via Relaxed Rank Minimization
- A convex program for mixed linear regression with a recovery guarantee for well-separated data
- Modal principal component analysis
- Dual principal component pursuit
- Robust PCA via regularized \textsc{Reaper} with a matrix-free proximal algorithm
- Anisotropic diffusion in consensus-based optimization on the sphere
- scientific article; zbMATH DE number 7370570 (Why is no real title available?)
- Asymptotic performance of PCA for high-dimensional heteroscedastic data
- Distributed Robust Subspace Recovery
- Computational and statistical tradeoffs via convex relaxation
- Fast, robust and non-convex subspace recovery
- Relaxation analysis in a data driven problem with a single outlier
- Robust iterative fitting of multilinear models
- A well-tempered landscape for non-convex robust subspace recovery
- Fast subspace approximation via greedy least-squares
- Weakly convex optimization over Stiefel manifold using Riemannian subgradient-type methods
- Efficient Convex Optimization for Non-convex Non-smooth Image Restoration
- Robust computation of linear models by convex relaxation
- Tractable algorithms for robust model estimation
- Stable camera motion estimation using convex programming
- Nonsmooth optimization over the Stiefel manifold and beyond: proximal gradient method and recent variants
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)
