SAMPLE CODE

Robust PCA Matrix Completion

Robust PCA

We provide MATLAB packages to solve the RPCA optimization problem by three different methods. All code below is Copyright 2009 Perception and Decision Lab, University of Illinois at Urbana-Champaign, and Microsoft Research Asia, Beijing. Please contact John Wright or Arvind Ganesh if you have any questions or comments.
  1. Augmented Lagrange Multiplier (ALM) Method [exact ALM - MATLAB zip] [inexact ALM - MATLAB zip]
    Usage -  The most basic form of the exact ALM function is [A, E] = exact_alm_rpca(D, λ), and that of the inexact ALM function is [A, E] = inexact_alm_rpca(D, λ), where D is a real matrix and λ is a positive real number. We solve the RPCA problem using the method of augmented Lagrange multipliers. The method converges Q-linearly to the optimal solution. The exact ALM algorithm is simple to implement, each iteration involves computing a partial SVD of a matrix the size of D, and converges to the true solution in a small number of iterations. The algorithm can be further speeded up by using a fast continuation technique, thereby yielding the inexact ALM algorithm.
    Reference - The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices, Z. Lin, M. Chen, L. Wu, and Y. Ma (UIUC Technical Report UILU-ENG-09-2215, November 2009).

  2. Accelerated Proximal Gradient [full SVD version - MATLAB zip] [partial SVD version - MATLAB zip]
    Usage -  The most basic form of the full SVD version of the function is [A, E] = proximal_gradient_rpca(D, λ), where D is a real matrix and λ is a positive real number. We consider a slightly different version of the original RPCA problem by relaxing the equality constraint. The algorithm is simple to implement, each iteration involves computing the SVD of a matrix the size of D, and converges to the true solution in a small number of iterations. The algorithm can be further speeded up by computing partial SVDs at each iteration. The most basic form of the partial SVD version of the function is [A, E] = partial_proximal_gradient_rpca(D, λ), where D is a real matrix and λ is a positive real number.
    Reference - Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix, Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma (UIUC Technical Report UILU-ENG-09-2214, August 2009).

  3. Dual Method [MATLAB zip]
    Usage - The most basic form of the function is [A, E] = dual_rpca(D, λ), where D is a real matrix and λ is a positive real number. We solve the convex dual of the RPCA problem, and retrieve the low-rank and sparse error matrices from the dual optimal solution. The algorithm computes only a partial SVD in each iteration and hence, scales well with the size of the matrix D.
    Reference - Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix, Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma (UIUC Technical Report UILU-ENG-09-2214, August 2009).

  4. Singular Value Thresholding [MATLAB zip]
    Usage - The most basic form of the function is [A, E] = singular_value_rpca(D, λ), where D is a real matrix and λ is a positive real number. Here again, we solve a relaxation of the original RPCA problem, albeit different from the one solved by the Accelerated Proximal Gradient (APG) method. The algorithm is extremely simple to implement, and the computational complexity of each iteration is about the same as that of the APG method. However, the number of iterations to convergence is typically quite large.
    Reference - Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization, J. Wright, A. Ganesh, S. Rao, and Y. Ma (UIUC Technical Report UILU-ENG-09-2210, April 2009).
Top of Page

Matrix Completion

We provide below links to publicly available code and references to solve the matrix completion problem faster than conventional algorithms.
  1. Augmented Lagrange Multiplier (ALM) Method [inexact ALM - MATLAB zip]
    Usage -  The most basic form of the inexact ALM function is A = inexact_alm_mc(D), where D is the incomplete matrix defined in the MATLAB sparse matrix format and the output A is a structure with two components - A.U and A.V (the left and right singular vectors scaled respectively by the square root of the corresponding non-zero singular values). Please refer to the file test_alm_mc.m for details on defining D appropriately. The algorithm is identical to the inexact ALM method described above to solve the RPCA prblem, and enjoys the same convergence properties.
    Reference - The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices, Z. Lin, M. Chen, L. Wu, and Y. Ma (UIUC Technical Report UILU-ENG-09-2215, November 2009).

  2. Singular Value Thresholding
    Reference - A Singular Value Thresholding Algorithm for Matrix Completion, J. -F. Cai, E. J. Candès, and Z. Shen (2008).

  3. OptSpace
    Reference - Matrix Completion from a Few Entries, R.H. Keshavan, A. Montanari, and S. Oh (2009).

  4. Accelerated Proximal Gradient
    Reference - An Accelerated Proximal Gradient Algorithm for Nuclear Norm Regularized Least Squares Problems, K. -C. Toh, and S. Yun (2009).

  5. Subspace Evolution and Transfer (SET) [MATLAB zip]
    Reference - SET: An Algorithm for Consistent Matrix Completion, W. Dai, and O. Milenkovic (2009).
Top of Page

If you would like to list your code related to this topic on this website, please contact the webmaster Arvind Ganesh.