Robust principal component analysis using facial reduction
Authors:
Open Access
- 27 November 2019
- journal article
- research article
- Published by Springer Nature in Optimization and Engineering
- Vol. 21 (3) , 1195-1219
Abstract
We introduce a novel approach for robust principal component analysis (RPCA) for a partially observed data matrix. The aim is to recover the data matrix as a sum of a low-rank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NP-hard in general. A classical approach to solving RPCA is to consider convex relaxations. One such heuristic involves the minimization of the (weighted) sum of a nuclear norm part, that promotes a low-rank component, with an $$\ell _1$$ norm part, to promote a sparse component. This results in a well-structured convex problem that can be efficiently solved by modern first-order methods. However, first-order methods often yield low accuracy solutions. Moreover, the heuristic of using a norm consisting of a weighted sum of norms may lose some of the advantages that each norm had when used separately. In this paper, we propose a novel nonconvex and nonsmooth reformulation of the original NP-hard RPCA model. The new model adds a redundant semidefinite cone constraint and solves small subproblems using a PALM algorithm. Each subproblem results in an exposing vector for a facial reduction technique that is able to reduce the size significantly. This makes the problem amenable to efficient algorithms in order to obtain high-level accuracy. We include numerical results that confirm the efficacy of our approach.
Keywords
This publication has 20 references indexed in Scilit:
- Application of Robust Principal Component Analysis (RPCA) to suppress erratic noise in seismic records2015
- Coordinate Shadows of Semidefinite and Euclidean Distance MatricesSIAM Journal on Optimization, 2015
- Robust PCA via Principal Component Pursuit: A review for a comparative evaluation in video surveillanceComputer Vision and Image Understanding, 2014
- Proximal alternating linearized minimization for nonconvex and nonsmooth problemsMathematical Programming, 2013
- Parallel stochastic gradient algorithms for large-scale matrix completionMathematical Programming Computation, 2013
- Fast alternating linearization methods for minimizing the sum of two convex functionsMathematical Programming, 2012
- Explicit Sensor Network Localization using Semidefinite Representations and Facial ReductionsSIAM Journal on Optimization, 2010
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm MinimizationSIAM Review, 2010
- On gradients of functions definable in o-minimal structuresAnnales de l'institut Fourier, 1998
- Reducibility among Combinatorial Problems1972