Fast algorithms for recovering a corrupted low-rank matrix
The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Abstract
This paper studies algorithms for solving the problem of recovering a low-rank matrix with a fraction of its entries arbitrarily corrupted. This problem can be viewed as a robust version of classical PCA, and arises in a number of application domains, including image processing, web data ranking, and bioinformatic data analysis. It was recently shown that under surprisingly broad conditions, it can be exactly solved via a convex programming surrogate that combines nuclear norm minimization and ¿1-norm minimization. This paper develops and compares two complementary approaches for solving this convex program. The first is an accelerated proximal gradient algorithm directly applied to the primal; while the second is a gradient algorithm applied to the dual problem. Both are several orders of magnitude faster than the previous state-of-the-art algorithm for this problem, which was based on iterative thresholding. Simulations demonstrate the performance improvement that can be obtained via these two algorithms, and clarify their relative merits.
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
Cites
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952 · cited 3×
“Recently, [15] demonstrated significant improvements for matrix completion [11], [12] by combining the judicious choice of Y k suggested by [7], [16] with continuation techniques.”
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Goodall, C. (1988) · Technometrics · doi:10.1080/00401706.1988.10488412 · Cited by 8,675
Jolliffe, I. T. (1986) · Springer Series in Statistics · doi:10.1007/978-1-4757-1904-8 · Cited by 8,273
A method for solving the convex programming problem with convergence rate O(1/k^2)
Nesterov, Y. E. (1983) · Доклады Академии наук · Cited by 6,318
A Singular Value Thresholding Algorithm for Matrix Completion
Cai, J.-F., Candès, E. J., & Shen, Z. (2010) · SIAM Journal on Optimization · doi:10.1137/080738970 · Cited by 5,809 · cited 1×
“Similar iterative thresholding techniques [10] can be applied to the problem of recovering a low-rank matrix from an incomplete (but clean) subset of its entries [11], [12].”
MethodExact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
The Approximation of One Matrix by Another of Lower Rank
Eckart, C., & Young, G. (1936) · Psychometrika · doi:10.1007/bf02288367 · Cited by 3,800 · cited 1×
“Correctly estimating this subspace is crucial for reducing the dimension of the data and facilitating tasks such as processing, analyzing, compressing, or visualizing the data [1], [2].”
BackgroundGuaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
Wright, J. N., Ganesh, A., Rao, S., Peng, Y., & Ma, Y. (2009) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1,495
Self-citationBregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,414
Toh, K.-C., & Yun, S. (2009) · National University of Singapore · Cited by 955
Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
Hale, E. T., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Optimization · doi:10.1137/070698920 · Cited by 909 · cited 1×
“So they do not scale well with the size of the matrix.”
BackgroundFast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix
Lin, Z., Ganesh, A., Wright, J. N., Wu, L., Chen, M., & Ma, Y. (2009) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 462
Self-citationLinearized Bregman iterations for compressed sensing
Cai, J., Osher, S., & Shen, Z. (2008) · Mathematics of Computation · doi:10.1090/s0025-5718-08-02189-3 · Cited by 351 · cited 1×
“One striking example of this is the current popularity of iterative thresholding algorithms for `1-norm minimization problems arising in compressed sensing [6]–[9].”
BackgroundLanczos Bidiagonalization With Partial Reorthogonalization
Larsen, R. M. (1998) · DAIMI Report Series · doi:10.7146/dpb.v27i537.7070 · Cited by 304 · cited 1×
“The soft-thresholding scalar operator S(.) in Algorithm 1 is defined as Sε[x] .= { sign(x) (|x| − ε) if |x| > ε, 0, otherwise, (4) and extended to vectors and matrices by applying it elementwise.”
BackgroundA generalized proximal point algorithm for certain non-convex minimization problems
FUKUSHIMA, M., & MINE, H. (1981) · International Journal of Systems Science · doi:10.1080/00207728108963798 · Cited by 166
A new singular value decomposition algorithm suited to parallelization and preliminary results
Konda, T., Takata, M., Iwasaki, M., & Nakamura, Y. (2006) · Cited by 15
Cited by
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-citationInfrared 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
Bouwmans, T., & Zahzah, E. H. (2014) · Computer Vision and Image Understanding · doi:10.1016/j.cviu.2013.11.009 · Cited by 463
Shen, Y., Wen, Z., & Zhang, Y. (2014) · Optimization Methods and Software · doi:10.1080/10556788.2012.700713 · Cited by 299
Robust Photometric Stereo via Low-Rank Matrix Completion and Recovery
Wu, L., Ganesh, A., Shi, B., Matsushita, Y., Wang, Y., & Ma, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-19318-7_55 · Cited by 298
Self-citation
Metadata
- Authors
- Ganesh, A., Lin, Z., Wright, J., Wu, L., Chen, M., & Ma, Y.
- Venue
- 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
- Publisher
- IEEE
- Published
- 2009-12
- Pages
- 213-216
- OpenAlex
- W1976632974
- Cited by
- 211
- References
- 18
- FWCI
- 22.61
- Type
- conference paper
- Language
- en
- Open access
- closed
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.