Non-convex Robust PCA

Praneeth Netrapalli; U N Niranjan; Sujay Sanghavi; Animashree Anandkumar; Prateek Jain

Source-linked AI summary

Non-convex Robust PCA

Praneeth Netrapalli, U N Niranjan, Sujay Sanghavi, Animashree Anandkumar, Prateek Jain

arXiv:1410.7660v1Oct 28, 2014cs.ITcs.LGstat.ML

TL;DR

Robust PCA seeks to recover a low-rank matrix from sparse corruptions despite PCA’s sensitivity to outliers. The paper uses alternating non-convex projections onto sparse and low-rank matrices, achieving convex-method recovery guarantees with lower computational cost and faster experimental performance.

Problem
Robust PCA addresses recovering a low-rank approximation after removing sparse corruptions, because ordinary PCA is sensitive to outliers.
Method
The method alternates projections of residuals onto sparse and low-rank matrices, using hard thresholding and singular value decomposition for efficiently computable non-convex projections.
Results
The method achieves global convergence and recovery conditions matching convex methods, while outperforming IALM in running time and providing faster, visually better foreground-background separation on real data.
Takeaways & Limitations
Non-convex robust PCA combines PCA-like computational scaling and convergence with recovery guarantees comparable to convex techniques.
Takeaways & Limitations
Unique recovery is impossible in general when the input matrix is itself both sparse and low rank.

Abstract

from arXiv · show

We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is {\em non-convex} but easy to compute. In spite of this non-convexity, we establish exact recovery of the low-rank matrix, under the same conditions that are required by existing methods (which are based on convex optimization). For an $m \times n$ input matrix ($m \leq n)$, our method has a running time of $O(r^2mn)$ per iteration, and needs $O(\log(1/ε))$ iterations to reach an accuracy of $ε$. This is close to the running time of simple PCA via the power method, which requires $O(rmn)$ per iteration, and $O(\log(1/ε))$ iterations. In contrast, existing methods for robust PCA, which are based on convex optimization, have $O(m^2n)$ complexity per iteration, and take $O(1/ε)$ iterations, i.e., exponentially more iterations for the same accuracy. Experiments on both synthetic and real data establishes the improved speed and accuracy of our method over existing convex implementations.

1 Introduction

Robust PCA decomposes an observed matrix into low-rank structure and sparse corruptions, addressing PCA’s sensitivity to outliers. The paper proposes a non-convex method that combines PCA-like efficiency with recovery guarantees matching convex approaches.

PCA is sensitive to outliers because it force-fits them into the low-rank approximation, motivating robust alternatives used across several applications.
Robust PCA decomposes M = L∗ + S∗ into sparse corruptions S∗ and a low-rank component L∗.
The proposed method alternates non-convex projections onto low-rank and sparse matrices, with O(r^2mn log(1/ε)) total runtime and O(log(1/ε)) iterations.
Its computational complexity nearly matches PCA when r is small, while its convergence rate is logarithmic rather than the O(1/ε) iterations required by convex methods.
The method provides global recovery guarantees matching convex techniques up to constants under stated sparsity and incoherence requirements.
Experiments report faster performance than IALM across tested settings and significantly faster, visually better foreground-background separation on real data.

2 Algorithm

AltProj solves robust PCA through efficient alternating non-convex projections onto sparse and low-rank matrix sets. Its stage-wise implementation achieves complexity close to vanilla PCA while retaining manageable convergence.

Algorithm: AltProj alternates projections of residuals onto sparse and low-rank matrices, using hard thresholding and singular value decomposition.The sparse projection uses hard thresholding, while the low-rank projection uses SVD.
Algorithm: The algorithm initializes by hard-thresholding M, then alternates rank-1 projections and progressively decreases the threshold.The initial threshold removes large entries before rank-1 projection, preventing large sparse perturbations from blocking progress.
Parameters: β is the algorithm’s main parameter and represents the expected spikiness of the low-rank component.The implementation reports β = 1/√n as an aggressive choice that speeds recovery.
Algorithm: Higher-rank projections are performed in stages from k = 1 to r, with iterations within each stage refining the estimates.The pseudocode takes matrix M, convergence criterion ϵ, target rank r, and thresholding parameter β as inputs.
Complexity: O(r^2mn log(1/ϵ)) is the overall complexity, because rank-k approximation costs O(kmn), there are at most r stages, and each stage uses O(log(1/ϵ)) iterations.This is a factor r from vanilla PCA’s O(rmn log(1/ϵ)) complexity.

3 Analysis

The analysis proves recovery under incoherence and sparsity conditions matching convex robust-PCA guarantees up to constants. Its proof establishes error contraction across alternating low-rank and sparse projections, while recognizing uniqueness and exact-rank boundaries.

Assumptions: The analysis assumes rank at most r, μ-incoherence of L*, and per-row and per-column sparsity bounded by α ≤ 1/(512μ^2r).These conditions constrain the low-rank component’s singular-vector structure and the density of sparse corruptions.
Limitations: Unique decomposition is not possible in general when the input is both sparse and low rank, so the stated conditions ensure uniqueness.A sparse perturbation can erase a structured low-rank block, demonstrating the boundary of recoverability.
Complexity: The computational analysis requires only rank-k approximations rather than exact singular vectors, so complexity does not depend on singular-value gaps.This property supports the method’s stated computational advantage.
Recovery: Theorem 1 establishes noiseless recovery under the stated conditions, with outputs bL and bS satisfying the theorem’s recovery guarantees.The paper states that these guarantees match convex-method conditions up to constant factors.
Convergence: O(log(1/ϵ)) iterations achieve error ϵ, compared with O(1/ϵ) iterations for the best known convex robust-PCA methods.The paper characterizes this as a linear convergence rate and a strongly polynomial method.
Noisy recovery: Theorem 2 extends recovery beyond exactly rank-r L* to noisy settings when additive noise has sufficiently small ℓ∞ norm.The noiseless theorem is presented as a special case of this noisy-recovery result.
Proof strategy: The proof alternates low-rank and sparse projections, showing that each reduces the corresponding ℓ∞ error before recursively repeating the argument.The low-rank projection controls perturbation from sparse errors, while the sparse projection contracts sparse-component error.

4 Experiments

The experiments evaluate AltProj on synthetic and video foreground-background separation data, comparing recovery, runtime, and visual quality with PCA and IALM. AltProj scales better as problem parameters increase and is substantially faster on real datasets.

Experimental setup: The study evaluates exact recovery and runtime against IALM using synthetic experiments averaged over 5 runs and real foreground-background separation videos.The synthetic comparisons vary sparsity, incoherence, and rank while fixing the other parameters.
Synthetic datasets: The experiments vary sparsity, incoherence, and rank while measuring time to reach relative error 10^-3.Synthetic data uses normally distributed low-rank factors and randomly sampled sparse support.
Synthetic datasets: AltProj scales significantly better than IALM as sparsity, incoherence, and rank increase.At sparse density α=0.4, IALM’s intermediate iterates can exceed rank 500 while the true rank is 5.
Real-world datasets: In the Escalator video, AltProj takes 63.2s versus 1688.9s for IALM and removes moving escalator steps from the extracted background.Both methods produce better foreground-background separation than PCA, whose result contains shadows and other artifacts.
Real-world datasets: In the Restaurant video, AltProj is around 19 times faster than IALM and produces a background without the noticeable blur seen in PCA and IALM.The reported computation times are 34.9s for AltProj and 693.2s for IALM.

5 Conclusion

The paper proposes non-convex alternating projections for robust PCA and establishes global convergence under conditions matching convex methods. It reports faster runtimes and superior experimental performance, while identifying random sparsity, random noise, and broader decomposition settings as open directions.

Conclusion: The method alternates projections onto low-rank and sparse matrices and achieves global convergence under conditions matching those for convex methods.The conclusion frames this as a non-convex robust PCA method.
Conclusion: The method has much faster running times and superior experimental performance than the convex methods.The conclusion also reports tight recovery guarantees for the sparse and low-rank components.
Future work: The analysis leaves random sparsity, improved random-noise recovery, and extensions to structured sparsity and robust tensor PCA for future investigation.These are explicitly identified as open questions beyond the demonstrated deterministic setting.

A Proof of Theorem 1

The proof establishes Theorem 1 by analyzing symmetric-matrix iterates, showing contraction and support control under incoherence and sparsity assumptions, then reducing the general rectangular case to the symmetric case.

Preliminaries: The proof uses Weyl’s inequality and Davis-Kahan perturbation results as preliminary tools for controlling eigenvalues and eigenvectors.The Davis-Kahan lemma is specialized to rank-1 matrices.
Iterative analysis: Lemma 7 bounds the entrywise error of the low-rank update, identified as the crucial step because ℓ∞ error bounds are difficult to obtain.The proof combines perturbation bounds, incoherence, and sparse-error control.
Iterative analysis: The induction establishes support containment for the sparse error and progressively stronger bounds on the low-rank and sparse iterates.The thresholding step and incoherence assumption support the base case and induction.
Iterative analysis: Algorithm 1 alternates L(t+1)=Pk(M−S(t)) with S(t+1)=Hζ(M−L(t+1)), and the analysis tracks E(t)=S∗−S(t).The proof proceeds by induction over iterations and stages.
Rectangular reduction: The general m×n problem is reduced to a symmetric problem by embedding the input into a larger symmetric matrix while preserving the required incoherence and sparsity conditions.The symmetric-case guarantee then proves the theorem for the original rectangular input.

B Proof of Theorem 2

The proof of Theorem 2 extends the contraction and support analysis to observations containing low-rank structure, dense corruption, and sparse errors. It then applies the same symmetric reduction to obtain guarantees for general rectangular matrices.

Generalized analysis: The proof bounds low-rank update errors using perturbation expansions together with bounds on N∗ and the sparse residual E(t).The analysis repeatedly combines matrix perturbation lemmas with incoherence and noise assumptions.
Inductive guarantee: The generalized induction controls both the support of the sparse error and the error bounds across iterations and stages.Lemma 14 provides the final iterate guarantees needed for the theorem.
Rectangular reduction: The rectangular case is reduced to the symmetric case by embedding M and preserving the theorem’s incoherence, dense-noise, and sparsity assumptions.The corresponding AltProj iterates retain analogous expressions under the embedding.

C Additional experimental results

The additional experiments examine intermediate ranks in IALM and compare NcRPCA with IALM on video foreground-background separation. NcRPCA achieves substantially shorter runtimes, with better or similar visual quality, while producing lower-rank low-rank solutions.

Synthetic datasets: Intermediate IALM iterates reach rank 800 even when the final output rank is 10.As rank, incoherence, or problem difficulty increases, soft thresholding produces higher-rank intermediate solutions and higher running times.
Experimental setup: The video experiments compare decompositions at relative error 10^-3 and report rank, sparsity, and computational time.Frames are vectorized and stacked column-wise before comparing the low-rank and sparse outputs.
Real-world datasets: 292.1s versus 783.4s: NcRPCA is faster than IALM on Shopping Mall while achieving better visual quality.NcRPCA avoids artifacts and shadows observed in IALM’s low-rank component.
Real-world datasets: 39.5s versus 989.0s: NcRPCA is faster than IALM on Curtain while achieving similar visual quality.NcRPCA returns rank 1 for L, whereas IALM returns rank 701.