PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Algorithms for Robust PCA via Gradient Descent

Xinyang Yi, Dohyung Park, Yudong Chen, Constantine Caramanis

arXiv:1605.07784v2cs.ITcs.LGmath.STstat.ML

TL;DR

Robust PCA must recover low-rank structure despite sparse corruptions, missing entries, and the computational limits of existing algorithms. This paper uses projected gradient descent on factorized variables with a sparse estimator, achieving improved fully observed runtime and near-linear-in-d runtime under partial observation when rank is small.

  • Problem

    Robust PCA seeks recovery despite missing and corrupted entries, where standard SVD is sensitive to outliers and scale.

  • Method

    The paper develops non-convex projected gradient algorithms on factorized spaces, paired with a sparse estimator for deterministic corruptions.

  • Results

    The fully observed algorithm runs in O(rd^2 log(1/ε)) time, improving the previous O(r^2d^2 log(1/ε)) complexity by a factor of r.

  • Takeaways & Limitations

    Partial-observation recovery uses O(µ^2r^2d log d) entries and O(µ^3r^4d log d log(1/ε)) time, enabling near-linear-in-d computation when r is small.

  • Takeaways & Limitations

    The fully observed robustness guarantee α = O(1/(µr√r)) is weaker by a factor √r than the optimal 1/(µr) guarantee.

Abstract

from arXiv · show

We consider the problem of Robust PCA in the fully and partially observed settings. Without corruptions, this is the well-known matrix completion problem. From a statistical standpoint this problem has been recently well-studied, and conditions on when recovery is possible (how many observations do we need, how many corruptions can we tolerate) via polynomial-time algorithms is by now understood. This paper presents and analyzes a non-convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, in the fully observed case, with $r$ denoting rank and $d$ dimension, we reduce the complexity from $\mathcal{O}(r^2d^2\log(1/\varepsilon))$ to $\mathcal{O}(rd^2\log(1/\varepsilon))$ -- a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than $\mathcal{O}(r^4d \log d \log(1/\varepsilon))$. Not only is this the best-known run-time for a provable algorithm under partial observation, but in the setting where $r$ is small compared to $d$, it also allows for near-linear-in-$d$ run-time that can be exploited in the fully-observed case as well, by simply running our algorithm on a subset of the observations.

1 Introduction

The paper targets robust PCA methods that handle corruptions and missing data while reducing the computational cost of provable recovery. It develops non-convex algorithms that improve runtime in fully and partially observed settings.

  • Motivation: PCA via SVD is vulnerable to missing entries, corrupted values, outliers, and large-scale computation.SVD minimizes squared error and has running time O(rd^2) for a rank-r approximation of a d-by-d matrix.
  • Related work: Existing robust PCA methods require O(r^2d^2) to O(d^3) time, while faster PCA methods lack robustness guarantees.The cited literature separates provable robustness from sub-quadratic computation.
  • Contribution: The paper proposes provably robust PCA algorithms with SVD-matching runtime and nearly linear dependence on dimension when rank is small.The nearly linear algorithm subsamples observations and extends to partial-observation Robust PCA.
  • Contribution: The deterministic corruption model assumes corruptions are spread across rows and columns to preserve low-rank identifiability.The paper develops a sparse estimator that exploits this spread-out structure.
  • Contribution: The fully observed algorithm achieves O(rd^2 log(1/ε)) complexity with robustness α = O(1/(µr^1.5)).This improves the previous algorithmic complexity by a factor of r under the stated setting.
  • Contribution: For partial observations, the method uses O(µ^2r^2d log d) entries and costs O(µ^3r^4d log d log(1/ε)), also yielding a matrix-completion guarantee.The savings can also reduce computation in fully observed problems when r is small.

2 Problem Setup

The problem is to recover a low-rank matrix and sparse corruptions from fully or partially observed data. The setup uses random erasures and imposes incoherence and spread-out corruption assumptions for identifiability.

  • Model: The observed matrix satisfies Y = M* + S*, where M* has rank r and S* has sparse support.In the partially observed setting, entries are independently revealed with probability p.
  • Partial observations: The support of observed entries is Φ = {(i,j) | Y(i,j) ≠ *}, and corruptions are assumed not to adapt to Φ.Unrevealed entries are represented by * under the Bernoulli observation model.
  • Assumptions: Identifiability requires M* not to be both low-rank and sparse, enforced through a µ-incoherence assumption.This excludes near-sparse or spiky low-rank matrices.
  • Assumptions: The corruption matrix belongs to Sα, meaning each row and column contains at most an α-fraction of nonzero entries.This spread-out condition constrains the support of S* rather than the magnitudes of its entries.

3 Algorithms

The algorithms use a two-phase procedure: initialize low-rank factors after sparse estimation, then alternate sparse estimation with projected gradient updates. The sparsification operator retains residual entries that are large in both their row and column, supporting the corruption model.

  • Initialization: The method first estimates Sinit with a sorting-based sparse estimator, then computes a rank-r factorization U0V0^⊤ from the residual.Initialization uses Sinit = Tα[Y] for full observations and Sinit = T2pα[Y] for partial observations, followed by an approximate rank-r SVD.
  • Gradient-based iterations: Each iteration estimates the sparse component St and applies projected gradient descent to the low-rank factors Ut and Vt.The same overall flow is used for full and partial observations, with implementation details differing between the two settings.
  • Sparse estimation: Tα[A] keeps entries that are simultaneously among the largest α-fraction in their row and column, guaranteeing Tα[A] ∈ Sα.This combines large residual magnitude with the assumption that each row and column contains at most an α-fraction of corruptions.
  • Optimization formulation: The loss is defined directly over the factorized variables U, V and sparse matrix S for fully and partially observed data.The fully observed objective uses the Frobenius reconstruction residual; the partial-observation objective is defined analogously on observed entries.
  • Optimization formulation: The optimization constrains U and V to preserve the incoherent structure expected of the recovered low-rank matrix.Row-norm constraints are based on the unavailable operator norm of M*, so the algorithm uses quantities derived from the initialization.

4 Main Results

The paper establishes convergence, robustness, and runtime guarantees for projected-gradient algorithms in fully and partially observed robust PCA. Subsampling preserves robustness while reducing dependence on dimension from quadratic to nearly linear in suitable regimes.

  • Fully observed setting: Theorems 1 and 2 establish initialization and geometric convergence guarantees for Algorithm 1 in the fully observed setting.With suitable initialization and step size, the gradient iteration contracts linearly and reaches relative precision ε in O(κ log(1/ε)) iterations.
  • Fully observed setting: O(κrd^2 log(1/ε)) is Algorithm 1’s runtime for ε accuracy, compared with O(r^2d^2 log(1/ε)) for AltProj when κ = O(1).The algorithm performs one rank-r SVD and computes gradients in O(rd^2) per iteration.
  • Robustness: α = O(1/(µr√r)) is the fully observed algorithm’s corruption tolerance under κ = O(1), a √r factor below the optimal 1/(µr) guarantee.The paper attributes this looseness to the initialization condition, while noting that sufficiently close initialization permits α = O(1/(µr)).
  • Partial observations: Algorithm 2 retains robustness under partial observations and achieves linear convergence with O(µrκ log(1/ε)) iterations.The guarantee holds with high probability under the observation conditions in Corollary 2; setting p = 1 recovers the fully observed result up to an additional µr factor in contraction.
  • Partial observations: O(µ^2r^2d log d) observed entries suffice, and the partial-observation model reduces to exact matrix completion when S* = 0.The stated sample complexity matches a positive semidefinite matrix-completion result by gradient descent and improves on cited non-convex alternatives.
  • Partial observations: O(µ^3r^4d log d log(1/ε)) is Algorithm 2’s runtime when the observed support has O(µ^2r^2d log d) entries.For r ≪ d^1/3, the paper recommends subsampling even fully observed data to obtain this near-linear dependence on d.

5 Numerical Results

Numerical experiments compare the proposed algorithms with AltProj and IALM on synthetic data and video foreground-background separation. The experiments show geometric convergence, linear dimension scaling under partial observation, lower computation, and effective background recovery.

  • Synthetic Datasets: Geometric convergence has a contraction factor nearly independent of the subsampling rate p.The fully observed setting corresponds to p = 1.
  • Synthetic Datasets: The running time scales linearly with d for partially observed data, consistent with the theory.At d = 2×10^5, approximately 0.1% of entries suffices for successful recovery, while competing methods manipulate all d^2 entries.
  • Synthetic Datasets: The proposed algorithm reaches the same accuracy with significantly less computation than AltProj and IALM.Using only a subset of entries provides additional speed-up.
  • Foreground-background Separation: The video experiments use Restaurant and ShoppingMall sequences with static backgrounds and sparse moving-object corruptions modeled as Robust PCA.Frames are vectorized and stacked as matrix columns.
  • Foreground-background Separation: The proposed algorithms achieve better running time than AltProj and IALM while separating persons from background images.Figure 3 reports recovery results for additional video frames.

6 Proofs

The proofs establish initialization and convergence properties for the proposed robust PCA algorithms. They combine sparse-estimation bounds, spectral perturbation arguments, incoherence, local descent, smoothness, and geometric error decay.

  • Proof of Theorem 1: The proofs bound the initialization error by relating Y − M* to the sparse corruption difference S* − Sinit.Sparse support properties yield operator- and infinity-norm control, which is combined with incoherence and Weyl-type singular-value perturbation bounds.
  • Proof of Theorem 1: The spectral initialization satisfies ||U0V0^T − M*||op ≤ 1/2 σ*r under αµr ≤ 1/(16κ).This bound supports the subsequent local convergence analysis.
  • Proof of Theorem 2: The analysis extends factorized gradient-descent arguments from symmetric positive semidefinite matrices to general asymmetric low-rank matrices.The proof uses local descent and smoothness properties around the optimal solution manifold.
  • Proof of Theorem 2: Under the stated initialization and corruption conditions, estimation error decays geometrically after each iteration.The proof maintains the iterates inside the local region by induction.
  • Proof of Theorem 2: Choosing T = O(κ log(1/ε)) iterations yields factorization error bounded by ε^2 times the initial distance.The final matrix-recovery guarantee follows from the relationship between factor distance and ||UTVT^T − M*||F.

6.5 Proof of Theorem 4

Theorem 4 is proved for partial observations by replacing the full-observation loss with a sampled loss and establishing analogous local descent and smoothness properties. The proof controls sampling, corruption supports, and factorization errors to obtain geometric convergence.

  • 6.5 Proof of Theorem 4: The partial-observation proof replaces L with sampled loss eL and uses a corresponding regularizer eG.The overall proof follows the full-observation argument while accounting for sampling effects.
  • 6.5 Proof of Theorem 4: The proof conditions on local descent and smoothness lemmas for eL, then shows error decreases in one iteration.The induction over iterations is inherited from the proof of Theorem 2.
  • 6.5 Proof of Theorem 4: Local descent follows by combining lower bounds for the sampled loss with upper bounds for regularization and error terms.The resulting inequalities establish the contraction needed for the partial-observation convergence theorem.
  • 6.5 Proof of Theorem 4: The analysis requires bounds on corruption density, initialization error, incoherence-related parameters, and the local factor distance.These conditions are encoded through parameters β, ϵ, α, κ, µ, r, and δt.
  • 6.5 Proof of Theorem 4: The sparse estimator controls the supports and magnitudes of S − S* using row- and column-wise sparsity together with bounds on sampled corruption supports.The proof separately bounds terms associated with sparse-estimation error and sampled low-rank error.

6.9 Proof of Lemma 4

The proof of Lemma 4 establishes that sampling preserves the relevant low-rank and sparse structure well enough to control the sampled gradient and support estimates. It combines projection, incoherence, sampling concentration, and row-column sparsity bounds.

  • Proof of Lemma 4: The sampled gradient is supported on Φ \ Ω because the sparse estimator removes entries on Ω.This support restriction enables separate control of observed residuals and sparse-estimation errors.
  • Proof of Lemma 4: Sampling preserves Frobenius norms of incoherent matrices whose row or column spaces match those of M*.The required sampling probability is controlled by an incoherence- and rank-dependent lower bound on p.
  • Proof of Lemma 4: The proof combines these sampling and sparsity controls with Cauchy–Schwarz and norm inequalities to bound the residual terms.The final bounds use the local assumptions on δ, γ, and ϵ.
  • Proof of Lemma 4: With high probability, the sampled corruption matrix has bounded nonzero counts per row and column.This support control is used to establish bounds for the sparse projection and sampled residuals.
  • Proof of Lemma 4: A second sampling lemma controls projections of small matrices onto Φ under row-norm constraints on U and V.Its conclusion is applied to bound sampled low-rank perturbations in the local analysis.

7 Proofs for Technical Lemmas

This section establishes technical inequalities and structural properties used in the paper’s main proofs, including concentration bounds, projection relations, and factor-alignment conditions.

  • Projection and norm bounds: The section develops technical lemmas for the main theorems, including bounds involving matrix projections and operator norms.A projection onto K is applied to matrices of the form L∗A⊤ + BR∗⊤, for which Π_KX = X.
  • Projection and norm bounds: 1 − 2d^-3: the projection inequality holds with high probability under the stated assumptions.
  • Sampling concentration: Bernstein’s inequality and a probabilistic union bound control row and column observation counts for independent binary sampling variables.The bounds apply to full and restricted supports, with analogous reasoning for columns.
  • Sampling concentration: With probability at least 1 − O(d^-3), the sampling operator satisfies the stated bound for every fixed matrix A.The argument then specializes A to the all-ones matrix and derives uniform row and column-count controls.
  • Factor alignment: The alignment minimizer is unique when the relevant singular values are positive, yielding symmetry and full-rank properties for the aligned factors.The proof characterizes the orthogonal alignment through an SVD and shows that F⊤Fπ∗ and (F − Fπ∗)⊤Fπ∗ are symmetric.
  • Factor alignment: ||F − Fπ∗||op < √2σ∗r ensures F⊤Fπ∗ has full rank and only positive singular values.

A Supporting Lemmas

This appendix collects supporting lemmas for low-rank factorization and sparse-support control, under explicit rank, spectral, and degree assumptions.

  • Factorization lemmas: Lemma 12 bounds factorization errors using ΔU := U − U∗ and ΔV := V − V∗.
  • Factorization lemmas: The factorization bound is further specialized to factors in U × V satisfying the conditions in (19).
  • Sparse-support control: Lemma 14 assumes each row and column of Ω contains at most an α fraction of entries and derives the corresponding sparse-support bound.The proof uses Lemma 13 to bound each entry of UV⊤ − U∗V∗⊤.
  • Spectral perturbation: The appendix defines σi(M) as the i-th largest singular value of M.
  • Spectral perturbation: Lemma 15 applies to two rank-r matrices whose operator-norm difference is at most 1/2σr(M1).

B Parameter Settings for FB Separation Experiments

The experiments specify RPCA parameters for FB separation and use a factor-based stopping rule for partial observation that avoids explicitly forming the full low-rank matrix.

  • RPCA parameters: r = 10, α = 0.2, and μ = 10 are used for the RPCA approximation of the FB separation problem.
  • Baseline settings: IALM uses λ = 1/√d1, while AltProj retains its default parameter settings and both methods use the stated stopping criterion.
  • Stopping criterion: The partial-observation algorithm never explicitly forms Mt = UtV⊤t, so the stopping criterion based on that matrix is inapplicable.
  • Stopping criterion: The alternative rule checks stability of low-rank factors and seeks a robust subspace capturing most of Y’s variance rather than enforcing an exact decomposition.
Loading 1605.07784v2…