PaperlayerView exact revision on arXiv

Source-linked AI summary

The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices

Zhouchen Lin, Minming Chen, Yi Ma

arXiv:1009.5055v3math.OCeess.SYmath.NA

TL;DR

Robust PCA must recover a low-rank matrix when even a few entries may be arbitrarily corrupted, a setting where classical PCA can fail badly. The paper develops exact and inexact augmented Lagrange multiplier algorithms, finding that IALM is consistently over five times faster than APG while achieving higher precision and using less memory.

  • Problem

    Robust PCA asks whether a low-rank matrix can be efficiently and accurately recovered when some entries are arbitrarily corrupted, even if corruption is sparse.

  • Method

    The paper develops exact and inexact augmented Lagrange multiplier algorithms for solving the Robust PCA convex program.

  • Results

    IALM is consistently over five times faster than APG in all Robust PCA simulations, with higher precision and often exact recovery of the corruption support.

  • Takeaways & Limitations

    ALM algorithms offer a simpler, more accurate, and less memory-intensive alternative to APG for large-scale Robust PCA and matrix completion.

  • Takeaways & Limitations

    The iterative-thresholding approach remains limited by its very large iteration count and difficult step-size selection.

Abstract

from arXiv · show

This paper proposes scalable and fast algorithms for solving the Robust PCA problem, namely recovering a low-rank matrix with an unknown fraction of its entries being arbitrarily corrupted. This problem arises in many applications, such as image processing, web data ranking, and bioinformatic data analysis. It was recently shown that under surprisingly broad conditions, the Robust PCA problem can be exactly solved via convex optimization that minimizes a combination of the nuclear norm and the $\ell^1$-norm . In this paper, we apply the method of augmented Lagrange multipliers (ALM) to solve this convex program. As the objective function is non-smooth, we show how to extend the classical analysis of ALM to such new objective functions and prove the optimality of the proposed algorithms and characterize their convergence rate. Empirically, the proposed new algorithms can be more than five times faster than the previous state-of-the-art algorithms for Robust PCA, such as the accelerated proximal gradient (APG) algorithm. Moreover, the new algorithms achieve higher precision, yet being less storage/memory demanding. We also show that the ALM technique can be used to solve the (related but somewhat simpler) matrix completion problem and obtain rather promising results too. We further prove the necessary and sufficient condition for the inexact ALM to converge globally. Matlab code of all algorithms discussed are available at http://perception.csl.illinois.edu/matrix-rank/home.html

1 Introduction · 2 Previous Algorithms for Matrix Recovery

The paper motivates Robust PCA as a scalable alternative to PCA for data with large, sparse corruptions and reviews iterative-thresholding methods for solving its convex formulation. It introduces ALM-based algorithms intended to improve convergence speed, accuracy, and partial-SVD efficiency.

  • 1 Introduction: PCA estimates a low-dimensional subspace by approximating data matrix D with a rank-constrained matrix A under Frobenius-norm error.The target dimension satisfies r ≪ min(m, n), and the model corresponds to i.i.d. Gaussian noise.
  • 1 Introduction: A single arbitrarily corrupted entry can make classical PCA’s estimate arbitrarily far from the true low-rank matrix.PCA performs well for small additive i.i.d. Gaussian noise but breaks down under large corruption, even when few observations are affected.
  • 1 Introduction: Robust PCA exactly recovers low-rank structure under broad conditions when the error matrix is sufficiently sparse, using nuclear-norm plus ℓ1-norm minimization.The convex program constrains D = A + E and weights the nuclear and entrywise ℓ1 norms with positive parameter λ.
  • 1 Introduction: Interior-point solvers do not scale to large matrices because their step-direction computation has complexity O(m6).The paper therefore motivates first-order methods that exploit the special structure of this convex optimization problem.
  • 1 Introduction: The paper presents exact and inexact augmented-Lagrange-multiplier methods for matrix recovery, with EALM proving Q-linear convergence and APG having only sub-linear convergence in theory.IALM is described as practically as fast as EALM while requiring significantly fewer partial SVDs.
  • 1 Introduction: IALM is often exact and more accurate than APG, which often leaves many small non-zero terms in E.This comparison is reported as an experimental result in the introduction.
  • 2 Previous Algorithms for Matrix Recovery: Section 2 summarizes existing algorithms for solving the Robust PCA matrix-recovery problem, providing context and a basis for comparison.The paper introduces this review as a completeness and comparison step before presenting its ALM algorithms.
  • 2.1 The Iterative Thresholding Approach: The iterative-thresholding approach solves a relaxed convex problem by alternately minimizing over A and E, then updating the multiplier using constraint violation.Its updates use soft-thresholding for vectors and matrices, including singular-value thresholding derived from the SVD.

Algorithm 1 (RPCA via Iterative Thresholding) · Algorithm 2 (RPCA via Accelerated Proximal Gradient) · 3 The Methods of Augmented Lagrange Multipliers

The section presents iterative-thresholding and accelerated proximal-gradient procedures for RPCA, then introduces augmented Lagrange multipliers as a general constrained-optimization framework. The algorithms use singular-value and entrywise thresholding, while acceleration achieves an O(k^-2) rate and continuation can speed convergence.

  • Algorithm 1 (RPCA via Iterative Thresholding): Algorithm 1 alternates singular-value thresholding for the low-rank component with entrywise thresholding for the sparse component, followed by a residual-based multiplier update.Each iteration computes an SVD of Y_{k−1}, forms A_k and E_k, and updates Y_k using D − A_k − E_k.
  • Algorithm 2 (RPCA via Accelerated Proximal Gradient): The accelerated proximal-gradient framework improves the basic gradient rate from O(k^-1) to O(k^-2), including for nonsmooth g.The stated objective-gap guarantee is F(X_k) − F(X*) ≤ Ck^-2.
  • Algorithm 2 (RPCA via Accelerated Proximal Gradient): APG applies directly to a relaxed RPCA problem and uses continuation by decreasing μ geometrically from μ_0 toward the floor μ̄.The continuation update is represented in Algorithm 2 by μ_{k+1} = max(ημ_k, μ̄), with η < 1.
  • Algorithm 2 (RPCA via Accelerated Proximal Gradient): The earlier dual approach solves RPCA through its dual and can recover the primal optimum while searching for a constrained steepest-ascent direction.That direction is obtained by projecting D onto the tangent cone of {Y | J(Y) ≤ 1}.
  • Algorithm 2 (RPCA via Accelerated Proximal Gradient): Algorithm 2 initializes primal variables and acceleration parameters, then iterates until convergence to output the low-rank and sparse components.The supplied algorithm fragment initializes A_0, A_{−1}, E_0, E_{−1}, and t_0, t_{−1} to zero or one.
  • Algorithm 2 (RPCA via Accelerated Proximal Gradient): A stated advantage of the dual approach is requiring only the principal singular space associated with the known largest singular value, rather than unknown leading singular values.The paper identifies efficient computation of this known singular space as the condition making the approach promising.
  • 3 The Methods of Augmented Lagrange Multipliers: The augmented-Lagrange-multiplier section defines a general method for constrained problems by constructing an augmented Lagrangian with positive parameter μ.Its convergence discussion assumes an increasing sequence {μ_k} and continuously differentiable f and h under general conditions.

Algorithm 3 (General Method of Augmented Lagrange Multiplier) · Algorithm 4 (RPCA via the Exact ALM Method)

The paper presents a general augmented Lagrange multiplier scheme and applies it to Robust PCA through the exact ALM method. It establishes convergence and optimality guarantees, then motivates an inexact variant that avoids solving each subproblem exactly.

  • Algorithm 3 (General Method of Augmented Lagrange Multiplier): ALM multipliers converge Q-linearly when {μ_k} is bounded and super-Q-linearly when {μ_k} is unbounded.The penalty parameter μ_k is also the proven optimal step size for updating Y_k.
  • Algorithm 4 (RPCA via the Exact ALM Method): For RPCA, ALM uses X = (A, E), f(X) = ∥A∥_* + λ∥E∥_1, and h(X) = D − A − E.These identifications define the augmented-Lagrangian formulation for matrix recovery.
  • Algorithm 4 (RPCA via the Exact ALM Method): Algorithm 4 applies ALM to RPCA and is called the exact ALM method because its inner subproblem is solved exactly.The algorithm initializes Y_0*, μ_0 > 0, ρ > 1, and iteratively updates the low-rank and sparse components.
  • Algorithm 4 (RPCA via the Exact ALM Method): Any accumulation point produced by Algorithm 4 is an optimal RPCA solution, with convergence rate at least O(μ^-1).If μ_k grows geometrically, EALM converges Q-linearly; faster growth can yield faster convergence, but larger μ_k can slow iterative thresholding.
  • Algorithm 4 (RPCA via the Exact ALM Method): Because SVD dominates computational cost, the sequence {μ_k} should be chosen to minimize the total number of SVDs.Numerical tests indicate that iterative thresholding for the exact subproblem can converge more slowly when μ_k is larger.
  • Algorithm 4 (RPCA via the Exact ALM Method): Updating A_k and E_k once per subproblem is sufficient for convergence to an optimal RPCA solution, motivating the inexact ALM method.The validity and optimality of this method are stated to follow from Theorem 2 under its specified condition, although the supplied passage truncates that condition.

Algorithm 5 (RPCA via the Inexact ALM Method)

Algorithm 5 applies inexact ALM to RPCA by alternating updates of the low-rank and corruption variables, then updating the multiplier and penalty parameter until convergence. Theorem 2 guarantees convergence but does not specify its rate, and the same framework extends to matrix completion.

  • Algorithm 5: The method initializes Y0, E0, µ0, ρ, and k, then iterates until convergence.The input is the observation matrix D and λ.
  • Algorithm 5: Each iteration approximately minimizes the augmented Lagrangian over A and E in alternating subproblems.The displayed steps specify updates for A and E using L(A, E, Yk, µk).
  • Algorithm 5: The algorithm updates Yk+1 = Yk + µk(D − Ak+1 − Ek+1), updates µk, increments k, and outputs (Ak, Ek).These steps enforce the RPCA decomposition constraint through the multiplier update.
  • Convergence: Theorem 2 guarantees convergence for inexact ALM but does not specify a convergence rate.This differs from Theorem 1 for the exact ALM method, which does specify the rate.
  • Matrix completion: For matrix completion, exact and inexact ALM approaches are similarly available, with πΩ(E) = 0 enforced during E minimization.The inexact matrix-completion procedure is given in Algorithm 6.

Algorithm 6 (Matrix Completion via the Inexact ALM Method)

Algorithm 6 applies the inexact augmented Lagrange multiplier method to matrix completion by alternating updates of the low-rank and error components, followed by multiplier and penalty-parameter updates. The paper states that the ALM convergence theorems extend to matrix completion, with multipliers remaining bounded and zero on unobserved entries.

  • Algorithm 6: Algorithm 6 initializes Y0 and E0, then iteratively updates the low-rank component, error component, multiplier, and penalty parameter until convergence.The output is the pair (A_k, E_k).
  • Algorithm 6: The error-component update maintains π̄_Ω(Y_k) = 0 throughout the iteration, so multiplier values at unknown entries remain zero.This property follows from the choice of E_k.
  • Convergence results: Theorems 1 and 2 extend to matrix completion, while Theorem 3 also applies because Y_k = π_Ω(Ŷ_k) and bounded {Ŷ_k} implies bounded {Y_k}.The proofs of Theorems 1 and 2 are omitted because they are similar to the corresponding arguments for the original problem.

4 Implementation Details

The implementation uses partial SVD with adaptive rank prediction, specialized truncation, and memory-saving matrix representations. It also specifies update-order guidance, stopping criteria, and algorithm parameters for RPCA and matrix completion.

  • Predicting the Dimension of Principal Singular Space: Partial SVD computes only singular values above the threshold, with Algorithm 5 predicting the principal singular-space dimension from the previous iteration.The prediction uses sv_k, the count svp_k of singular values exceeding μ_k^-1, d = min(m,n), and sv_0 = 10.
  • Predicting the Dimension of Principal Singular Space: Algorithm 6 initializes Y and A as zero matrices and uses singular-value growth and gap information to make the estimated rank monotonically increase toward the true rank.The truncation rules add up to 10 singular values when needed and cap the estimate using the largest detected singular-value gap.
  • Order of Updating A and E: Numerical tests recommend updating E before A in Algorithms 4 and 5 because the order can slightly change the iterations needed for the same accuracy.The recommendation accounts for the high SVD cost on large matrices.
  • Memory Saving for Algorithm 6: Sparse D and Y_k storage, together with A = LR^T and implicit E_k, substantially reduces memory because only π_Ω(A_k) is needed.L and R have size m × svp_k, and the small percentage of samples enables the memory savings.
  • Choosing Parameters: Algorithm 5 uses ε1 = 10^-7 and ε2 = 10^-5, whereas Algorithm 6 uses ε1 = 10^-7 and ε2 = 10^-6.The implementations also set Algorithm 4’s μ0 = 0.5/||sgn(D)||2 and ρ = 6, Algorithm 5’s μ0 = 1.25/||D||2 and ρ = 1.6, and Algorithm 6’s μ0 = 1/||D||2.

5 Simulations · 6 Conclusions · A Proofs and Technical Details for Section 3

The simulations show that ALM methods outperform competing APG, SVT, and APGL algorithms on Robust PCA and matrix completion, while the conclusions emphasize accuracy, convergence, and implementation advantages. The appendix supplies mathematical details supporting the Section 3 theorems.

  • 5 Simulations: Simulations generate random low-rank and sparse-corruption matrices with λ = m^-1/2, comparing ALM methods against APG for Robust PCA.The experiments use a common workstation and random Gaussian factors, uniformly supported corruptions, and entries in [-500,500].
  • 5 Simulations: Five times faster: IALM is at least five times faster than APG, while EALM and IALM achieve higher accuracy and estimate ||E*||_0 near ground truth.APG often substantially overestimates the number of nonzeros in E*, whereas EALM and IALM remain extremely close.
  • 5 Simulations: IALM is always faster than SVT and outperforms APGL when the sampling density p/m^2 exceeds 10%.The comparison concerns matrix completion using SVT and APGL, with APGL defined as APG with line search.
  • 6 Conclusions: The paper proposes EALM and IALM for Robust PCA, and IALM is consistently over five times faster than APG in all simulations.Both algorithms are reported as faster than the previous state-of-the-art APG algorithm.
  • 6 Conclusions: For matrix completion, IALM is considerably faster than SVT and faster than APGL when the percentage of available entries is greater than 10%.The conclusion qualifies the APGL advantage as applying when availability is not too low.
  • 6 Conclusions: ALM methods are simpler to analyze, easier to implement, more accurate, and less storage-intensive than accelerated proximal gradient methods.Their iterations are proven to converge to the exact solution even when the penalty parameter does not approach infinity, whereas APG normally solves a relaxed problem approximately.
  • A Proofs and Technical Details for Section 3: The appendix provides mathematical details for Section 3 and prepares results in Sections A.1 and A.2 to prove Theorems 1 and 2.These preparatory results support the appendix’s proofs of the Section 3 convergence and optimality claims.

A.1 Relationship between Primal and Dual Norms · A.2 Boundedness of Some Sequences

The appendix relates subgradients to dual norms and uses this relationship to establish boundedness of sequences required by the convergence theorems. It also records storage differences between IALM and APG for RPCA and matrix completion.

  • A.2 Boundedness of Some Sequences: Theorem 4 is the stated basis for the lemmas that establish boundedness of sequences needed by the convergence theorems.The appendix explicitly introduces the boundedness requirement before presenting the theorem and then derives lemmas from it.
  • A.1 Relationship between Primal and Dual Norms: IALM uses one fewer intermediate dense matrix than APG for RPCA, while APG uses two additional low-rank matrices and one additional sparse matrix for matrix completion.The comparison is based on smart reuse of intermediate matrices, which makes the codes harder to read.
  • A.1 Relationship between Primal and Dual Norms: For matrix completion, IALM handled A* of size 104 × 104 and rank 102 on the authors’ workstation, whereas APG could not.This numerical result is presented as evidence of the memory difference between the methods.
  • A.1 Relationship between Primal and Dual Norms: For a real Hilbert space, any subgradient y of the norm at nonzero x has dual norm ∥y∥*=1, while at x=0 it is at most 1.The result is stated as Theorem 4 for y ∈ ∂∥x∥.
  • A.1 Relationship between Primal and Dual Norms: For nonzero x, selecting w=0, 2x yields the stated dual-norm conclusion used in the norm relationship argument.The supplied passage presents this choice as an intermediate deduction.
  • A.2 Boundedness of Some Sequences: The sequences {Y*k}, {Yk}, and {Ŷk} are all bounded, with Ŷk defined as Yk−1+μk−1(D−Ak−Ek−1).The boundedness lemma includes the displayed definition of Ŷk.
  • A.2 Boundedness of Some Sequences: The proof invokes the optimality of A* and Theorem 4 to establish the sequence-boundedness result.The supplied proof passages identify optimality of A* and Theorem 4 as the relevant steps.
  • A.2 Boundedness of Some Sequences: The boundedness of {Y*k} follows from the dual norms of ∥· ∥* and ∥· ∥1 being ∥· ∥2 and ∥· ∥∞, respectively.The boundedness of {Yk} and {Ŷk} is stated to follow similarly.

A.3 Proof of Theorem 1 · A.4 Key Lemmas

Theorem 1 is established by proving that the recovered pair is optimal for RPCA and that the algorithm has the stated convergence rate. The key lemmas provide the identities and monotonicity properties underlying this analysis.

  • A.3 Proof of Theorem 1: The proof concludes that (A*, E*) is an optimal solution to the RPCA problem.
  • A.3 Proof of Theorem 1: The proof combines the triangular inequality of norms with equation (36) to establish the convergence rate.
  • A.4 Key Lemmas: A key lemma states an identity involving successive differences of Y, E, and A relative to the optimal primal and dual solutions.The optimal solutions are (A*, E*) for RPCA and Y* for its dual problem.
  • A.4 Key Lemmas: The identity is derived using A* + E* = D and the relation D − A_{k+1} − E_{k+1} = μ_k^-1.
  • A.4 Key Lemmas: Lemma 3 establishes that the subgradient of a convex function is a monotone operator.The proof follows directly from the definition of subgradient by adding two inequalities.
  • A.4 Key Lemmas: Lemma 4 states that, when μ_k is nondecreasing, each entry of the specified series is nonnegative and the series sum is finite.
  • A.4 Key Lemmas: Using the Lagrangian saddle-point property and Lemma 3, the analysis shows that {∥E_k − E*∥_F^2} is non-increasing.The Lagrangian is L(A, E, Y) = ∥A∥_* + λ∥E∥_1 + ⟨Y, D − A − E⟩.

A.5 Proof of Theorem 2

The proof handles Algorithm 5 by separating bounded and diverging penalty sequences. When μ_k → +∞, it establishes feasibility of accumulation points and convergence toward an optimal RPCA solution, with A_k → A* under vanishing constraint residuals.

  • Case analysis: When {μ_k} is upper bounded, Algorithm 5 is already known to converge from prior work.The proof therefore focuses on the case μ_k → +∞.
  • Feasibility: k∥Y_k − Y_{k−1}∥_F → 0, so every accumulation point of (A_k, E_k) is feasible.Feasibility follows from the vanishing scaled multiplier difference.
  • Optimality: A subsequence (A_kj, E_kj) approaches an optimal solution (A*, E*) of the RPCA problem.The argument uses the optimal objective value f* and subgradient inequalities for the nuclear and ℓ^1 norms.
  • Limit identification: As D − A_k − E_k → 0 and D = A* + E*, the proof concludes that A_k → A*.The vanishing constraint residual identifies the limiting low-rank component with A*.

A.6 Proof of Theorem 3

The proof establishes boundedness of the multiplier sequences and uses this to show that {E_k} is Cauchy and therefore convergent. It also identifies a bad-initialization case in which E_k does not converge to E*.

  • Boundedness: {Y_k} and {Ŷ_k} are bounded sequences, with ∥Y_k∥_F ≤ C and ∥Ŷ_k∥_F ≤ C.Lemma 1 supplies a common constant C bounding both sequences in Frobenius norm.
  • Convergence: {E_k} is a Cauchy sequence and therefore has a limit E_∞.The proof derives the Cauchy property before asserting convergence to E_∞.
  • Initialization condition: If Algorithm 5 is badly initialized, E_k does not converge to E*.The proof explicitly states this as a limitation of the initialization.
Loading 1009.5055v3…