Exact matrix completion via convex optimization
The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Abstract
Suppose that one observes an incomplete subset of entries selected from a low-rank matrix. When is it possible to complete the matrix and recover the entries that have not been seen? We demonstrate that in very general settings, one can perfectly recover all of the missing entries from most sufficiently large subsets by solving a convex programming problem that finds the matrix with the minimum nuclear norm agreeing with the observed entries. The techniques used in this analysis draw upon parallels in the field of compressed sensing, demonstrating that objects other than signals and images can be perfectly reconstructed from very limited information.
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
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,591
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673
Horn, R. A., & Johnson, C. R. (1991) · Cambridge University Press eBooks · doi:10.1017/cbo9780511840371 · Cited by 9,319
Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Sturm, J. F. (1999) · Optimization Methods and Software · doi:10.1080/10556789908805766 · Cited by 7,377
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921
Self-citationNear-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
Candes, E. J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.885507 · Cited by 6,839
Bollobás, B. (1985) · Cited by 6,196
Cited by
Halko, N., Martinsson, P. G., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,002
Geometric Deep Learning: Going beyond Euclidean data
Bronstein, M. M., Bruna, J., LeCun, Y., Szlam, A., & Vandergheynst, P. (2017) · IEEE Signal Processing Magazine · doi:10.1109/msp.2017.2693418 · Cited by 3,661
“Mathematically, a recommendation method can be posed as a matrix completion problem [92], where columns and rows represent users”
MethodTensor 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
The Power of Convex Relaxation: Near-Optimal Matrix Completion
Candes, E. J., & Tao, T. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2044061 · Cited by 2,060
Recovering Gene Interactions from Single-Cell Data Using Data Diffusion
van Dijk, D., Sharma, R., Nainys, J., Yim, K., Kathail, P., Carr, A. J., Burdziak, C., Moon, K. R., Chaffer, C. L., Pattabiraman, D., et al. (2018) · Cell · doi:10.1016/j.cell.2018.05.061 · Cited by 1,829
Aldoseri, A., Al-Khalifa, K. N., & Hamouda, A. M. (2023) · Applied Sciences · doi:10.3390/app13127082 · Cited by 716
CayleyNets: Graph Convolutional Neural Networks With Complex Rational Spectral Filters
Levie, R., Monti, F., Bresson, X., & Bronstein, M. M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2879624 · Cited by 685
Accelerated Dynamic MRI Exploiting Sparsity and Low-Rank Structure: k-t SLR
Lingala, S. G., Hu, Y., DiBella, E., & Jacob, M. (2011) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2010.2100850 · Cited by 664
Matrix completion from a few entries
Keshavan, R. H., Oh, S., & Montanari, A. (2009) · 2009 IEEE International Symposium on Information Theory · doi:10.1109/isit.2009.5205567 · Cited by 650
Image Inpainting : Overview and Recent Advances
Guillemot, C., & Le Meur, O. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2273004 · Cited by 608
An accelerated gradient method for trace norm minimization
Ji, S., & Ye, J. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553434 · Cited by 517
On Adaptive Attacks to Adversarial Example Defenses
Tramer, F., Carlini, N., Brendel, W., & Madry, A. (2020) · arXiv · doi:10.48550/arxiv.2002.08347 · Cited by 486
Hong, M., Razaviyayn, M., Luo, Z.-Q., & Pang, J.-S. (2016) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2481563 · Cited by 447
Detecting False Data Injection Attacks on Power Grid by Sparse Optimization
Liu, L., Esmalifalak, M., Ding, Q., Emesih, V. A., & Han, Z. (2014) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2013.2284438 · Cited by 446
A useful variant of the Davis–Kahan theorem for statisticians
Yu, Y., Wang, T., & Samworth, R. J. (2015) · Biometrika · doi:10.1093/biomet/asv008 · Cited by 441
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
Chi, Y., Lu, Y. M., & Chen, Y. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2937282 · Cited by 360
“(31) One parameter that plays a crucial role in determining the feasibility of matrix completion is a certain coherence measure, defined as follows [1].”
BackgroundInfluentialYang, 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
Average Case Analysis of Multichannel Sparse Recovery Using Convex Relaxation
Eldar, Y. C., & Rauhut, H. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2034789 · Cited by 356
LRTV: MR Image Super-Resolution With Low-Rank and Total Variation Regularizations
Shi, F., Cheng, J., Wang, L., Yap, P.-T., & Shen, D. (2015) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2015.2437894 · Cited by 315
Robust 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
A Tutorial on Environment-Aware Communications via Channel Knowledge Map for 6G
Zeng, Y., Chen, J., Xu, J., Wu, D., Xu, X., Jin, S., Gao, X., Gesbert, D., Cui, S., & Zhang, R. (2024) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2024.3364508 · Cited by 303
Signal Recovery on Graphs: Variation Minimization
Chen, S., Sandryhaila, A., Moura, J. M. F., & Kovacevic, J. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2441042 · Cited by 294
Udell, M., Horn, C., Zadeh, R., & Boyd, S. (2016) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000055 · Cited by 245
“an unknown m × n matrix A of low rank r from just about nr log2 n noisy samples Ω with an error that is proportional to the noise level [23, 24, 117, 22], so long as the matrix A satisfies a certain incoherence condition and the samples Ω are chosen uniformly at random.”
BackgroundTensor Completion Algorithms in Big Data Analytics
Song, Q., Ge, H., Caverlee, J., & Hu, X. (2019) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/3278607 · Cited by 229
“In matrix case, Bernoulli sampling [26] or independent sampling with replacement [164] are always assumed to simply the random sampling approach.”
BackgroundInfluential
Metadata
- Authors
- Candès, E., & Recht, B.
- Venue
- Communications of the ACM
- Published
- 2012-06
- Volume
- 55
- Issue
- 6
- Pages
- 111-119
- ISSN
- 0001-0782 (ISSN-L)
- 1557-7317
- OpenAlex
- W2124608575
- Cited by
- 996
- References
- 50
- FWCI
- 71.17
- Type
- journal article
- 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.