The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Exact Matrix Completion via Convex Optimization
Open accessAbstract
We consider a problem of considerable practical interest: the recovery of a data matrix from a sampling of its entries. Suppose that we observe m entries selected uniformly at random from a matrix M. Can we complete the matrix and recover the entries that we have not seen? We show that one can perfectly recover most low-rank matrices from what appears to be an incomplete set of entries. We prove that if the number m of sampled entries obeys $$m\ge C\,n^{1.2}r\log n$$ for some positive numerical constant C, then with very high probability, most n×n matrices of rank r can be perfectly recovered by solving a simple convex optimization program. This program finds the matrix with minimum nuclear norm that fits the data. The condition above assumes that the rank is not too large. However, if one replaces the 1.2 exponent with 1.25, then the result holds for all values of the rank. Similar results hold for arbitrary rectangular matrices as well. Our results are connected with the recent literature on compressed sensing, and show 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.
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
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639
Cited by
Knowledge Graph Embedding: A Survey of Approaches and Applications
Wang, Q., Mao, Z., Wang, B., & Guo, L. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2754499 · Cited by 2,654
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
Machine Learning Methods That Economists Should Know About
Athey, S., & Imbens, G. W. (2019) · Annual Review of Economics · doi:10.1146/annurev-economics-080217-053433 · Cited by 1,163
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
Matrix Completion Methods for Causal Panel Data Models
Athey, S., Bayati, M., Doudchenko, N., Imbens, G., & Khosravi, K. (2018) · doi:10.3386/w25132 · Cited by 497
Latent variable graphical model selection via convex optimization
Chandrasekaran, V., Parrilo, P. A., & Willsky, A. S. (2012) · The Annals of Statistics · doi:10.1214/11-aos949 · Cited by 377
Non-convex Optimization for Machine Learning
Jain, P., & Kar, P. (2017) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000058 · Cited by 364
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
Geometric median and robust estimation in Banach spaces
Minsker, S. (2015) · Bernoulli · doi:10.3150/14-bej645 · Cited by 261
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
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
An Exact and Robust Conformal Inference Method for Counterfactual and Synthetic Controls
Chernozhukov, V., Wüthrich, K., & Zhu, Y. (2021) · Journal of the American Statistical Association · doi:10.1080/01621459.2021.1920957 · Cited by 176
Implicit Regularization in Matrix Factorization
Gunasekar, S., Woodworth, B., Bhojanapalli, S., Neyshabur, B., & Srebro, N. (2018) · 2018 Information Theory and Applications Workshop (ITA) · doi:10.1109/ita.2018.8503198 · Cited by 170
Modality-correlation-aware sparse representation for RGB-infrared object tracking
Lan, X., Ye, M., Zhang, S., Zhou, H., & Yuen, P. C. (2020) · Pattern Recognition Letters · doi:10.1016/j.patrec.2018.10.002 · Cited by 121
Mendel: the Swiss army knife of genetic analysis programs
Lange, K., Papp, J. C., Sinsheimer, J. S., Sripracha, R., Zhou, H., & Sobel, E. M. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt187 · Cited by 109
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
Thung, K.-H., Yap, P.-T., & Shen, D. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-67558-9_19 · Cited by 63
Low-Rank Matrix Completion for Topological Interference Management by Riemannian Pursuit
Shi, Y., Zhang, J., & Letaief, K. B. (2016) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2016.2544758 · Cited by 56
Causal models for longitudinal and panel data: a survey
Arkhangelsky, D., & Imbens, G. (2024) · The Econometrics Journal · doi:10.1093/ectj/utae014 · Cited by 50
Spinner, M. A., Aleshin, A., Santaguida, M. T., Schaffert, S. A., Zehnder, J. L., Patterson, A. S., Gekas, C., Heiser, D., & Greenberg, P. L. (2020) · Blood Advances · doi:10.1182/bloodadvances.2020001934 · Cited by 40
Subspace Estimation from Unbalanced and Incomplete Data Matrices: 𝓁2, ∞ Statistical Guarantees
Cai, C., Li, G., Chi, Y., Poor, H. V., & Chen, Y. (2021) · The Annals of Statistics · doi:10.1214/20-aos1986 · Cited by 37
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
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
Metadata
- Authors
- Candès, E. J., & Recht, B.
- Venue
- Foundations of Computational Mathematics
- Published
- 2009-04-03
- Volume
- 9
- Issue
- 6
- Pages
- 717-772
- ISSN
- 1615-3375 (ISSN-L)
- 1615-3383
- OpenAlex
- W2611328865
- Cited by
- 4,877
- References
- 1
- FWCI
- 177.07
- Type
- journal article
- Language
- en
- Open access
- hybrid
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.
