The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
A Singular Value Thresholding Algorithm for Matrix Completion
Open accessAbstract
This paper introduces a novel algorithm to approximate the matrix with minimum nuclear norm among all matrices obeying a set of convex constraints. This problem may be understood as the convex relaxation of a rank minimization problem and arises in many important applications as in the task of recovering a large matrix from a small subset of its entries (the famous Netflix problem). Off-the-shelf algorithms such as interior point methods are not directly amenable to large problems of this kind with over a million unknown entries. This paper develops a simple first-order and easy-to-implement algorithm that is extremely efficient at addressing problems in which the optimal solution has low rank. The algorithm is iterative, produces a sequence of matrices $\{\boldsymbol{X}^k,\boldsymbol{Y}^k\}$, and at each step mainly performs a soft-thresholding operation on the singular values of the matrix $\boldsymbol{Y}^k$. There are two remarkable features making this attractive for low-rank matrix completion problems. The first is that the soft-thresholding operation is applied to a sparse matrix; the second is that the rank of the iterates $\{\boldsymbol{X}^k\}$ is empirically nondecreasing. Both these facts allow the algorithm to make use of very minimal storage space and keep the computational cost of each iteration low. On the theoretical side, we provide a convergence analysis showing that the sequence of iterates converges. On the practical side, we provide numerical examples in which $1,000\times1,000$ matrices are recovered in less than a minute on a modest desktop computer. We also demonstrate that our approach is amenable to very large scale problems by recovering matrices of rank about 10 with nearly a billion unknowns from just about 0.4% of their sampled entries. Our methods are connected with the recent literature on linearized Bregman iterations for $\ell_1$ minimization, and we develop a framework in which one can understand these algorithms in terms of well-known Lagrange multiplier algorithms.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Functions of Matrices: Theory and Computation
Higham, N. J. (2008) · doi:10.1137/1.9780898717778 · Cited by 2,113
Randomized algorithms for the low-rank approximation of matrices
Liberty, E., Woolfe, F., Martinsson, P.-G., Rokhlin, V., & Tygert, M. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0709640104 · Cited by 559
Cited by
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
LoRA: Low-Rank Adaptation of Large Language Models
Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., & Chen, W. (2021) · arXiv · doi:10.48550/arxiv.2106.09685 · Cited by 13,453
Weighted Nuclear Norm Minimization with Application to Image Denoising
Gu, S., Zhang, L., Zuo, W., & Feng, X. (2014) · 2014 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2014.366 · Cited by 2,316
Return of Frustratingly Easy Domain Adaptation
Sun, B., Feng, J., & Saenko, K. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10306 · Cited by 2,004
Genome-wide association studies of brain imaging phenotypes in UK Biobank
Elliott, L. T., Sharp, K., Alfaro-Almagro, F., Shi, S., Miller, K. L., Douaud, G., Marchini, J., & Smith, S. M. (2018) · Nature · doi:10.1038/s41586-018-0571-7 · Cited by 834
Anomaly Detection in Hyperspectral Images Based on Low-Rank and Sparse Representation
Xu, Y., Wu, Z., Li, J., Plaza, A., & Wei, Z. (2016) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2015.2493201 · Cited by 602
Siegel, E. H., Sands, M. K., Van den Noortgate, W., Condon, P., Chang, Y., Dy, J., Quigley, K. S., & Barrett, L. F. (2018) · Psychological Bulletin · doi:10.1037/bul0000128 · Cited by 515
Non-convex Optimization for Machine Learning
Jain, P., & Kar, P. (2017) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000058 · Cited by 364
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
Missing Modalities Imputation via Cascaded Residual Autoencoder
Tran, L., Liu, X., Zhou, J., & Jin, R. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.528 · Cited by 256
Canonical Tensor Decomposition for Knowledge Base Completion
Lacroix, T., Usunier, N., & Obozinski, G. (2018) · arXiv · doi:10.48550/arxiv.1806.07297 · Cited by 247
Data poisoning attacks on factorization-based collaborative filtering
Li, B., Wang, Y., Singh, A., & Vorobeychik, Y. (2016) · arXiv · doi:10.48550/arxiv.1608.08182 · Cited by 235
DC formulations and algorithms for sparse optimization problems
Gotoh, J.-Y., Takeda, A., & Tono, K. (2018) · Mathematical Programming · doi:10.1007/s10107-017-1181-0 · Cited by 184
Surface Defect Detection via Entity Sparsity Pursuit With Intrinsic Priors
Wang, J., Li, Q., Gan, J., Yu, H., & Yang, X. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2019.2917522 · Cited by 141
Incomplete multi-modal representation learning for Alzheimer’s disease diagnosis
Liu, Y., Fan, L., Zhang, C., Zhou, T., Xiao, Z., Geng, L., & Shen, D. (2021) · Medical Image Analysis · doi:10.1016/j.media.2020.101953 · Cited by 102
Thung, K.-H., Yap, P.-T., Adeli, E., Lee, S.-W., & Shen, D. (2018) · Medical Image Analysis · doi:10.1016/j.media.2018.01.002 · Cited by 89
Transfer learning for cross-language text categorization through active correspondences construction
Zhou, J., Pan, S., Tsang, I., & Ho, S.-S. (2016) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v30i1.10211 · Cited by 50
AdaLoRA: Adaptive Budget Allocation for Parameter-Efficient Fine-Tuning
Zhang, Q., Chen, M., Bukharin, A., Karampatziakis, N., He, P., Cheng, Y., Chen, W., & Zhao, T. (2023) · arXiv · doi:10.48550/arxiv.2303.10512 · Cited by 47
Burn scar detection using cloudy MODIS images via low-rank and sparsity-based models
Dao, M., Kwan, C., Ayhan, B., & Tran, T. D. (2016) · 2016 IEEE Global Conference on Signal and Information Processing (GlobalSIP) · doi:10.1109/globalsip.2016.7905827 · Cited by 42
Direct parametric reconstruction from undersampled (k,t)-space data in dynamic contrast enhanced MRI
Dikaios, N., Arridge, S., Hamy, V., Punwani, S., & Atkinson, D. (2014) · Medical Image Analysis · doi:10.1016/j.media.2014.05.001 · Cited by 40
Computation of Two-Dimensional Spectra Assisted by Compressed Sampling
Almeida, J., Prior, J., & Plenio, M. B. (2012) · The Journal of Physical Chemistry Letters · doi:10.1021/jz3009369 · Cited by 24
Data Imputation in Epistatic MAPs by Network-Guided Matrix Completion
Žitnik, M., & Zupan, B. (2015) · Journal of Computational Biology · doi:10.1089/cmb.2014.0158 · Cited by 14
Sparsity-Aware Learning and Compressed Sensing: An Overview
Theodoridis, S., Kopsinis, Y., & Slavakis, K. (2014) · Academic Press Library in Signal Processing · doi:10.1016/b978-0-12-396502-8.00023-1 · Cited by 14
Information retrieval, fusion, completion, and clustering for employee expertise estimation
Horesh, R., Varshney, K. R., & Yi, J. (2016) · 2016 IEEE International Conference on Big Data (Big Data) · doi:10.1109/bigdata.2016.7840746 · Cited by 14
Power Quality Disturbance Classification based on Adaptive Compressed Sensing and Machine Learning
Cheng, L., Wu, Z., Xuanyuan, S., & Chang, H. (2020) · 2020 IEEE Green Technologies Conference(GreenTech) · doi:10.1109/greentech46478.2020.9289735 · Cited by 11
Metadata
- Authors
- Cai, J.-F., Candès, E. J., & Shen, Z.
- Venue
- SIAM Journal on Optimization
- Published
- 2010-01
- Volume
- 20
- Issue
- 4
- Pages
- 1956-1982
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2103972604
- Cited by
- 5,809
- References
- 3
- FWCI
- 191.70
- 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.
