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

DOI10.1007/S00365-014-9242-6zbMATH Open1318.62161arXiv1012.4116OpenAlexW1574877207MaRDI QIDQ485350FDOQ485350

Authors: Gilad Lerman, Teng Zhang 

Publication date: 9 January 2015

Published in: Constructive Approximation (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)