On the robust PCA and Weiszfeld's algorithm

DOI10.1007/S00245-019-09566-1zbMATH Open1468.62302arXiv1902.04292OpenAlexW2913810924MaRDI QIDQ2019909FDOQ2019909

Max Nimmer, S. Setzer, Gabriele Steidl, Sebastian Neumayer

Publication date: 22 April 2021

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: Principal component analysis (PCA) is a powerful standard tool for reducing the dimensionality of data. Unfortunately, it is sensitive to outliers so that various robust PCA variants were proposed in the literature. This paper addresses the robust PCA by successively determining the directions of lines having minimal Euclidean distances from the data points. The corresponding energy functional is not differentiable at a finite number of directions which we call anchor directions. We derive a Weiszfeld-like algorithm for minimizing the energy functional which has several advantages over existing algorithms. Special attention is paid to the careful handling of the anchor directions, where we take the relation between local minima and one-sided derivatives of Lipschitz continuous functions on submanifolds of $mathbb{R}^d$ into account. Using ideas for stabilizing the classical Weiszfeld algorithm at anchor points and the Kurdyka-{L}ojasiewicz property of the energy functional, we prove global convergence of the whole sequence of iterates generated by the algorithm to a critical point of the energy functional. Numerical examples demonstrate the very good performance of our algorithm.

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

zbMATH Keywords

robust principal component analysisWeiszfeld algorithmKurdyka-Lojasiewicz propertyrobust subspace recovery

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Factor analysis and principal components; correspondence analysis (62H25) Numerical mathematical programming methods (65K05) Quadratic programming (90C20)

Cites Work

• The elements of statistical learning. Data mining, inference, and prediction
• Fast, robust and non-convex subspace recovery
• Robust Statistics
• Robust principal component analysis?
• Projection algorithms for nonconvex minimization with application to sparse principal component analysis
• Projection-Pursuit Approach to Robust Dispersion Matrices and Principal Components: Primary Theory and Monte Carlo
• Title not available (Why is that?)
• Robust Statistics
• Robust Statistics
• On the Convergence of a Class of Iterative Methods for Solving the Weber Location Problem
• Convex Analysis
• A note on Fermat's problem
• A Majorize–Minimize Strategy for Subspace Optimization Applied to Image Restoration
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Robust PCA via Outlier Pursuit
• Title not available (Why is that?)
• On gradients of functions definable in o-minimal structures
• Two proposals for robust PCA using semidefinite programming
• Weiszfeld's method: old and new results
• Local convergence in Fermat's problem
• Robust computation of linear models by convex relaxation
• Robust \(\ell_1\) approaches to computing the geometric median and principal and independent components
• Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming
• Conditional Gradient Algorithmsfor Rank-One Matrix Approximations with a Sparsity Constraint
• A modified Weiszfeld algorithm for the Fermat-Weber location problem
• Robust recovery of multiple subspaces by geometric \(l_{p}\) minimization
• Principal component analysis for Riemannian manifolds, with an application to triangular shape spaces
• On vector and matrix median computation
• Optimization over geodesics for exact principal geodesic analysis
• \(l_p\)-recovery of the most significant subspace among multiple subspaces with outliers
• Scale space and variational methods in computer vision. 6th international conference, SSVM 2017, Kolding, Denmark, June 4--8, 2017. Proceedings
• Technical note: Directional derivatives in nonsmooth optimization
• On the rotational invariant \(L_1\)-norm PCA
• Optimal Algorithms for <formula formulatype="inline"> <tex Notation="TeX">$L_{1}$</tex></formula>-subspace Signal Processing
• Barycentric subspace analysis on manifolds
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Sample-limited \(L_p\) barycentric subspace analysis on constant curvature spaces
• Efficient L1-Norm Principal-Component Analysis via Bit Flipping

Cited In (3)

• On orthogonal projections for dimension reduction and applications in augmented target loss functions for learning problems
• Robust PCA and pairs of projections in a Hilbert space
• Robust PCA via regularized \textsc{Reaper} with a matrix-free proximal algorithm

Uses Software

• robustbase
• ElemStatLearn
• FMS

This page was built for publication: On the robust PCA and Weiszfeld's algorithm

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