Non-convex Robust PCA

By Praneeth Netrapalli, Uma-Naresh Niranjan, Sujay Sanghavi, Anima Anandkumar, Prateek Jain. Neural Information Processing Systems, 2014

299 citations recorded by the source corpus.

We propose a new provable method for robust PCA, where the task is to recover a low-rank matrix, which is corrupted with sparse perturbations. Our method consists of simple alternating projections onto the set of low rank and sparse matrices with intermediate de-noising steps. We prove correct recovery of the low rank and sparse components under tight recovery conditions, which match those for the state-of-art convex relaxation techniques. Our method is extremely simple to implement and has low computational complexity. For a $m \times n$ input matrix (say m \geq n), our method has O(r^2 mn\log(1/\epsilon)) running time, where $r$ is the rank of the low-rank component and $\epsilon$ is the accuracy. In contrast, the convex relaxation methods have a running time O(mn^2/\epsilon), which is not scalable to large problem instances. Our running time nearly matches that of the usual PCA (i.e. non robust), which is O(rmn\log (1/\epsilon)). Thus, we achieve ``best of both the worlds'', viz low computational complexity and provable recovery for robust PCA. Our analysis represents one of the few instances of global convergence guarantees for non-convex methods.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/52f7361f37a7f13185c9e4885cb6c26e61608616

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation (2015, methodology): “Using the formulation (1.3) and replacing the ℓ0 norm by its well-known convex surrogate, the ℓ1 norm, we have min U∈Rm×r ,V ∈Rr×n ||M − UV ||1 = ∑ i,j |Mij − (UV )ij |, (1.4) which we will refer to as ℓ1-LRA.”
Phase Retrieval Using Alternating Minimization (2013, background): “We would like to stress that not only does a natural variant of our proposed algorithm have rigorous theoretical guarantees, it also is eﬀective practically as each of its iterations is fast, has a closed form solution and does not require SVD computation.”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, background): “joint alignment [24], learning shallow neural networks [103,132], robust subspace learning [34,74,86,91].”
Complete dictionary recovery over the sphere (2015, result): “The particular geometry of this problem does not demand any clever initialization, in contrast with most recent approaches to analyzing nonconvex recovery of structured signals [9–11, 13, 18–30].”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “robust PCA [159] low-rank projection + thresholding [25] [7, 8, 213, 214] GD + thresholding [64, 215] alternating minimization [216] spectrum estimation — projected GD [217] [218, 219]”
Simple, Efficient, and Neural Algorithms for Sparse Coding (2015, background): “This adds to the recent literature on analyzing alternating minimization Jain et al. (2013); Hardt (2013); Netrapalli et al. (2013, 2014) but these work in a setting where there is a convex program that is known to work too, and in our setting, the only known convex program runs in time exponential…”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery (2017, methodology): “Parameter setting for AltProj [8].”
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems (2015, background): “suchentry-wiseobservationscanalsobecastasrank-onemeasurementsof X. Therefore,the precedingmodiﬁedTWFmayaddtorecentliteratureinapplyingnon-convexschemesforlow-rankmatrix completion [42–45], robust PCA [46], or even a broader family of latent-variable models (e.g. dictionary learning[47,48],sparsecodi”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “[273] proposed a Non-convex Alternating Projections algorithm (AltProj) to solve a non-convex formulation of RPCA.”
A Geometric Analysis of Phase Retrieval (2016, methodology): “Besides GPR studied here, this line of work includes low-rank matrix recovery [35,52,53,59,60,63,77,89,98,99,107,113], tensor recovery [7–9,44, 61], structured element pursuit [55,85], dictionary learning [3,4,10–12,96], mixed regression [90,110], blind deconvolution [67–69], super resolution [40], ”
Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “[37]–[39]), sparse PCA [40], [41], robust PCA [42] and EM (ExpectedMaximization) algorithm [43], [44].”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, methodology): “Sun and Luo [2015], Zheng and Lafferty [2016]) accomplished this by showing a geometric property which is very similar to strong convexity holds in the neighborhood of optimal solution.”
Low rank approximation with entrywise l1-norm error (2017, background): “We also mention why a related objective function, robust PCA [19, 20, 72, 73, 93, 96], does not give a provable approximation factor for `1low rank approximation.”
Provable Dynamic Robust PCA or Robust Subspace Tracking (2017, unknown): “The standard RPCA problem has been extensively studied [2]–[4], [6], [8], [18].”