l_p-recovery of the most significant subspace among multiple subspaces with outliers

DOI10.1007/S00365-014-9242-6MaRDI QIDQ485350zbMATH OpenOpenAlexFDO

Authors Gilad Lerman, Teng Zhang

Publication date 9 January 2015

Published in Constructive Approximation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1012.4116

zbMATH Keywords

robust statisticsgeometric probability\(l_p\) minimizationbest approximating subspacehybrid linear modelingoptimization on the Grassmannian

Mathematics Subject Classification ID

Nonparametric robustness (62G35) Pattern recognition, speech recognition (68T10) Geometric probability and stochastic geometry (60D05) Computational learning theory (68Q32)

Abstract: We assume data sampled from a mixture of d-dimensional linear subspaces with spherically symmetric distributions within each subspace and an additional outlier component with spherically symmetric distribution within the ambient space (for simplicity we may assume that all distributions are uniform on their corresponding unit spheres). We also assume mixture weights for the different components. We say that one of the underlying subspaces of the model is most significant if its mixture weight is higher than the sum of the mixture weights of all other subspaces. We study the recovery of the most significant subspace by minimizing the lp-averaged distances of data points from d-dimensional subspaces, where p>0. Unlike other lp minimization problems, this minimization is non-convex for all p>0 and thus requires different methods for its analysis. We show that if 0<p<=1, then for any fraction of outliers the most significant subspace can be recovered by lp minimization with overwhelming probability (which depends on the generating distribution and its parameters). We show that when adding small noise around the underlying subspaces the most significant subspace can be nearly recovered by lp minimization for any 0<p<=1 with an error proportional to the noise level. On the other hand, if p>1 and there is more than one underlying subspace, then with overwhelming probability the most significant subspace cannot be recovered or nearly recovered. This last result does not require spherically symmetric outliers.

Recommendations

• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Dual principal component pursuit
• Sampling-based dimension reduction for subspace approximation with outliers
• Fast, robust and non-convex subspace recovery
• A novel M-estimator for robust PCA

Cites work

• scientific article; zbMATH DE number 51391 (Why is no real title available?)
• scientific article; zbMATH DE number 1302567 (Why is no real title available?)
• scientific article; zbMATH DE number 739280 (Why is no real title available?)
• scientific article; zbMATH DE number 194744 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• A geometric analysis of subspace clustering with outliers
• A novel M-estimator for robust PCA
• An Analysis of the Total Approximation Problem in Separable Norms, and an Algorithm for the Total $l_1 $ Problem
• Connect the dots: how many random points can a regular curve pass through?
• DIFFERENTIAL GEOMETRY OF GRASSMANN MANIFOLDS
• Fast, robust and non-convex subspace recovery
• For most large underdetermined systems of equations, the minimal 𝓁₁‐norm near‐solution approximates the sparsest near‐solution
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Hybrid linear modeling via local best-fit flats
• Invertibility of symmetric random matrices
• Least orthogonal absolute deviations
• On orthogonal linear \(\ell_1\) approximation
• On the Gauss-Newton method for l1 orthogonal distance regression
• Orthogonal linear regression algorithm based on augmented matrix formulation
• Robust PCA via Outlier Pursuit
• Robust Statistics
• Robust Statistics
• Robust principal component analysis for functional data. (With comments)
• Robust principal component analysis?
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Robust subspace clustering
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Spectral clustering based on local linear approximations
• Stable signal recovery from incomplete and inaccurate measurements
• The Geometry of Algorithms with Orthogonality Constraints
• The Method of Least Squares and Some Alternatives: Part I
• The Method of Least Squares and Some Alternatives: Part II
• The Minimum in the Gamma Function
• The best bounds in Gautschi-Kershaw inequalities
• The finite dimensional basis problem with an appendix on nets of Grassmann manifolds
• Two proposals for robust PCA using semidefinite programming

Cited in

(6)

• Dual principal component pursuit
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Robust computation of linear models by convex relaxation
• A well-tempered landscape for non-convex robust subspace recovery
• Similarity matrix framework for data from union of subspaces
• On the robust PCA and Weiszfeld's algorithm

Describes a project that uses

Uses Software

• robustbase
• FMS

This page was built for publication: \(l_p\)-recovery of the most significant subspace among multiple subspaces with outliers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q485350)