The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
Open accessPreprint — published as 10.1016/j.jsb.2012.10.010 · Paper page
The DOI matches its OpenAlex record.
Abstract
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
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Robust Recovery of Subspace Structures by Low-Rank Representation
Liu, G., Lin, Z., Yan, S., Sun, J., Yu, Y., & Ma, Y. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.88 · Cited by 3,594
Self-citationLearning Deep CNN Denoiser Prior for Image Restoration
Zhang, K., Zuo, W., Gu, S., & Zhang, L. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.300 · Cited by 2,116
Tensor Completion for Estimating Missing Values in Visual Data
Liu, J., Musialski, P., Wonka, P., & Ye, J. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.39 · Cited by 2,063
Adamson, B., Norman, T. M., Jost, M., Cho, M. Y., Nuñez, J. K., Chen, Y., Villalta, J. E., Gilbert, L. A., Horlbeck, M. A., Hein, M. Y., et al. (2016) · Cell · doi:10.1016/j.cell.2016.11.048 · Cited by 1,193
“We applied recent advances in sparse matrix theory (Candès et al., 2011; Lin et al., 2010) to decompose the observed gene expression matrix (X) into a low-rank matrix (L), representing the lowdimensional dynamics of the population, and a sparse matrix (S), capturing noise and effects that are…”
Visual Domain Adaptation: A survey of recent advances
Patel, V. M., Gopalan, R., Li, R., & Chellappa, R. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2347059 · Cited by 899
RASL: Robust Alignment by Sparse and Low-Rank Decomposition for Linearly Correlated Images
Peng, Y., Ganesh, A., Wright, J., Xu, W., & Ma, Y. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.282 · Cited by 817
Self-citationCompressive Sensing via Nonlocal Low-Rank Regularization
Dong, W., Shi, G., Li, X., Ma, Y., & Huang, F. (2014) · IEEE Transactions on Image Processing · doi:10.1109/tip.2014.2329449 · Cited by 598
Self-citationLow-Rank Tensor Constrained Multiview Subspace Clustering
Zhang, C., Fu, H., Liu, S., Liu, G., & Cao, X. (2015) · 2015 IEEE International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2015.185 · Cited by 566
On Unifying Multi-view Self-Representations for Clustering by Tensor Multi-rank Minimization
Xie, Y., Tao, D., Zhang, W., Liu, Y., Zhang, L., & Qu, Y. (2018) · International Journal of Computer Vision · doi:10.1007/s11263-018-1086-2 · Cited by 506
Multiview Clustering: A Scalable and Parameter-Free Bipartite Graph Fusion Method
Li, X., Zhang, H., Wang, R., & Nie, F. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3011148 · Cited by 499
Infrared Small Target Detection via Non-Convex Rank Approximation Minimization Joint l2,1 Norm
Zhang, L., Peng, L., Zhang, T., Cao, S., & Peng, Z. (2018) · Remote Sensing · doi:10.3390/rs10111821 · Cited by 484
Hyperspectral Image Restoration Via Total Variation Regularized Low-Rank Tensor Decomposition
Wang, Y., Peng, J., Zhao, Q., Leung, Y., Zhao, X.-L., & Meng, D. (2018) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2017.2779539 · Cited by 484
Laplacian Regularized Low-Rank Representation and Its Applications
Yin, M., Gao, J., & Lin, Z. (2016) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2462360 · Cited by 442
Self-citationWeighted Schatten $p$ -Norm Minimization for Image Denoising and Background Subtraction
Xie, Y., Gu, S., Liu, Y., Zuo, W., Zhang, W., & Zhang, L. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2599290 · Cited by 412
Yang, J., Luo, L., Qian, J., Tai, Y., Zhang, F., & Xu, Y. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2016.2535218 · Cited by 360
Discriminative Transfer Subspace Learning via Low-Rank and Sparse Representation
Xu, Y., Fang, X., Wu, J., Li, X., & Zhang, D. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2510498 · Cited by 336
Kronecker-Basis-Representation Based Tensor Sparsity and Its Applications to Tensor Recovery
Xie, Q., Zhao, Q., Meng, D., & Xu, Z. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2734888 · Cited by 318
Non-negative low rank and sparse graph for semi-supervised learning
Zhuang, L., Gao, H., Lin, Z., Ma, Y., Zhang, X., & Yu, N. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247944 · Cited by 316
Self-citationTransfer adaptation learning: A decade survey
Zhang, L., & Gao, X. (2024) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3183326 · Cited by 314
“matrix recovery [170], [171] and sparse subspace clustering (SSC) [172], [173], [174].”
BackgroundRobust visual domain adaptation with low-rank reconstruction
Jhuo, I.-H., Liu, D., Lee, D. T., & Chang, S.-F. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247924 · Cited by 308
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm
Lu, C., Tang, J., Yan, S., & Lin, Z. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2511584 · Cited by 307
Self-citationRobust view transformation model for gait recognition
Zheng, S., Zhang, J., Huang, K., He, R., & Tan, T. (2011) · 2011 18th IEEE International Conference on Image Processing · doi:10.1109/icip.2011.6115889 · Cited by 301
Generalized Transfer Subspace Learning Through Low-Rank Constraint
Shao, M., Kit, D., & Fu, Y. (2014) · International Journal of Computer Vision · doi:10.1007/s11263-014-0696-6 · Cited by 298
Learning a Joint Affinity Graph for Multiview Subspace Clustering
Tang, C., Zhu, X., Liu, X., Li, M., Wang, P., Zhang, C., & Wang, L. (2019) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2018.2889560 · Cited by 288
Street-to-shop: cross-scenario clothing retrieval via parts alignment and auxiliary set
Liu, S., Song, Z., Wang, M., Xu, C., Lu, H., & Yan, S. (2012) · Proceedings of the 20th ACM international conference on Multimedia · doi:10.1145/2393347.2396471 · Cited by 283
Smooth PARAFAC Decomposition for Tensor Completion
Yokota, T., Zhao, Q., & Cichocki, A. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2586759 · Cited by 279
A Simple Prior-Free Method for Non-rigid Structure-from-Motion Factorization
Dai, Y., Li, H., & He, M. (2014) · International Journal of Computer Vision · doi:10.1007/s11263-013-0684-2 · Cited by 270
Graph and Total Variation Regularized Low-Rank Representation for Hyperspectral Anomaly Detection
Cheng, T., & Wang, B. (2020) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2019.2936609 · Cited by 266
LSDT: Latent Sparse Domain Transfer Learning for Visual Adaptation
Zhang, L., Zuo, W., & Zhang, D. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2016.2516952 · Cited by 255
On the Applications of Robust PCA in Image and Video Processing
Bouwmans, T., Javed, S., Zhang, H., Lin, Z., & Otazo, R. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2853589 · Cited by 255
Self-citationRobust Face Recognition via Adaptive Sparse Representation
Wang, J., Lu, C., Wang, M., Li, P., Yan, S., & Hu, X. (2014) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2014.2307067 · Cited by 235
“Inspired by the optimization method used in [39] and [40], we adopt alternating direction method (ADM) [41] to solve problem (13).”
MethodInfluentialChen, Y., He, W., Yokoya, N., & Huang, T.-Z. (2020) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2936042 · Cited by 229
Low-rank matrix recovery with structural incoherence for robust face recognition
Chen, C.-F., Wei, C.-P., & Wang, Y.-C. F. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247981 · Cited by 215
“Augmented Lagrange multipliers (ALM) have been applied to solve the standard LR problem [3, 13].”
MethodInfluentialGeneralized Singular Value Thresholding
Lu, C., Zhu, C., Xu, C., Yan, S., & Lin, Z. (2015) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v29i1.9464 · Cited by 196
Self-citationUnsupervised Visual Hashing with Semantic Assistant for Content-Based Image Retrieval
Zhu, L., Shen, J., Xie, L., & Cheng, Z. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2562624 · Cited by 186
“This study proposes an optimization algorithm based on augmented Lagrangian multiplier [26] to calculate the optimal solution.”
BackgroundMethodInfluentialMatrix Completion for Weakly-Supervised Multi-Label Image Classification
Cabral, R., De la Torre, F., Costeira, J. P., & Bernardino, A. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2343234 · Cited by 173
Bilinear Factor Matrix Norm Minimization for Robust PCA: Algorithms and Applications
Shang, F., Cheng, J., Liu, Y., Luo, Z.-Q., & Lin, Z. (2018) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2748590 · Cited by 172
“We also compare our methods with several state-of-the-art methods, such as LMaFit3 [47], RegL14 [16], Unifying [49], factEN5 [15], RPCA6 [44], PSVT7 [45], WNNM8 [46], and LpSq9 [31].”
BackgroundMethodInfluentialSelf-citationCognitive processing of a common stimulus synchronizes brains, hearts, and eyes
Madsen, J., & Parra, L. C. (2022) · PNAS Nexus · doi:10.1093/pnasnexus/pgac020 · Cited by 91
Metadata
- Authors
- Lin, Z., Chen, M., & Ma, Y.
- Venue
- Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign)
- Publisher
- arXiv
- Published
- 2010
- arXiv
- 1009.5055
- OpenAlex
- W6929385289
- Cited by
- 1,176
- References
- 0
- FWCI
- 27.79
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.