Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis

DOI10.1109/TSP.2017.2749215MaRDI QIDQ4628127zbMATH OpenOpenAlexFDO

Authors George K. Atia, Mostafa Rahmani

Publication date 6 March 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: This paper presents a remarkably simple, yet powerful, algorithm termed Coherence Pursuit (CoP) to robust Principal Component Analysis (PCA). As inliers lie in a low dimensional subspace and are mostly correlated, an inlier is likely to have strong mutual coherence with a large number of data points. By contrast, outliers either do not admit low dimensional structures or form small clusters. In either case, an outlier is unlikely to bear strong resemblance to a large number of data points. Given that, CoP sets an outlier apart from an inlier by comparing their coherence with the rest of the data points. The mutual coherences are computed by forming the Gram matrix of the normalized data points. Subsequently, the sought subspace is recovered from the span of the subset of the data points that exhibit strong coherence with the rest of the data. As CoP only involves one simple matrix multiplication, it is significantly faster than the state-of-the-art robust PCA algorithms. We derive analytical performance guarantees for CoP under different models for the distributions of inliers and outliers in both noise-free and noisy settings. CoP is the first robust PCA algorithm that is simultaneously non-iterative, provably robust to both unstructured and structured outliers, and can tolerate a large number of unstructured outliers.

Recommendations

• Principle component analysis: robust versions
• Fast algorithms for robust principal component analysis with an upper bound on the rank
• Robust principal component analysis: a factorization-based approach with linear complexity
• Efficient algorithms for robust and stable principal component pursuit problems
• Accelerated Alternating Projections for Robust Principal Component Analysis
• Fast multidimensional completion and principal component analysis methods via the cosine product
• Projection-pursuit based principal component analysis: a large sample theory
• The FastHCS algorithm for robust PCA

Cited in

(6)

• Fast computation of robust subspace estimators
• Rare-event detection by Quasi-Wang-Landau Monte Carlo sampling with approximate Bayesian computation
• A well-tempered landscape for non-convex robust subspace recovery
• Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset
• Double \(\mathrm{L}_{2, \mathrm{p}}\)-norm based PCA for feature extraction
• [[:Publication:6173530|Tensor Robust Principal Component Analysis via Tensor Fibered Rank and \({\boldsymbolTemplate:L p}\) Minimization]]

This page was built for publication: Coherence Pursuit: Fast, Simple, and Robust Principal Component Analysis

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