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

Mathematics – Optimization and Control

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

23 pages. This manuscript first appeared as University of Illinois at Urbana-Champaign technical report #UILU-ENG-09-2215 in O

Scientific paper

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

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-561199

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.