The DOI matches its Crossref record; 25 of the 25 references it cites were found in a registry or an index.
Matrix completion from a few entries
Abstract
Let M be an n¿ × n matrix of rank r ¿ n, and assume that a uniformly random subset E of its entries is observed. We describe an efficient algorithm that reconstructs M from |E| = O(r n) observed entries with relative root mean square error RMSE ¿ C(¿) (nr/|E|)1/2. Further, if r = O(1) and M is sufficiently unstructured, then it can be reconstructed exactly from |E| = O(n log n) entries. This settles (in the case of bounded rank) a question left open by Candes and Recht and improves over the guarantees for their reconstruction algorithm. The complexity of our algorithm is O(|E|r log n), which opens the way to its use for massive data sets. In the process of proving these statements, we obtain a generalization of a celebrated result by Friedman-Kahn-Szemeredi and Feige-Ofek on the spectrum of sparse random matrices.
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,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
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
Guaranteed 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
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A., Arias, T. A., & Smith, S. T. (1998) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479895290954 · Cited by 2,685
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
Minimization of functions having Lipschitz continuous first partial derivatives
Armijo, L. (1966) · Pacific Journal of Mathematics · doi:10.2140/pjm.1966.16.1 · Cited by 1,983
Candes, E. J., & Plan, Y. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2035722 · Cited by 1,709
Regularization methods for learning incomplete matrices
Mazumder, R., Hastie, T. J., & Tibshirani, R. J. (2009) · Journal of Machine Learning Research · doi:10.48550/arxiv.0906.2034 · Cited by 1,640
Cited by
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
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
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
Candes, E. J., & Plan, Y. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2035722 · Cited by 1,709
Recommendation systems: Principles, methods and evaluation
Isinkaye, F. O., Folajimi, Y. O., & Ojokoh, B. A. (2015) · Egyptian Informatics Journal · doi:10.1016/j.eij.2015.06.005 · Cited by 1,326
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
Exact matrix completion via convex optimization
Candès, E., & Recht, B. (2012) · Communications of the ACM · doi:10.1145/2184319.2184343 · Cited by 996
Lü, L., Medo, M., Yeung, C. H., Zhang, Y.-C., Zhang, Z.-K., & Zhou, T. (2012) · Physics Reports · doi:10.1016/j.physrep.2012.02.006 · Cited by 995
Matrix Completion From a Few Entries
Keshavan, R. H., Montanari, A., & Oh, S. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2046205 · Cited by 974
Self-citationFast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization
Hu, Y., Zhang, D., Ye, J., Li, X., & He, X. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.271 · Cited by 829
Low-rank matrix completion using alternating minimization
Jain, P., Netrapalli, P., & Sanghavi, S. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488693 · Cited by 817
Wen, Z., Yin, W., & Zhang, Y. (2012) · Mathematical Programming Computation · doi:10.1007/s12532-012-0044-1 · Cited by 774
The Optimal Hard Threshold for Singular Values is \(4/\sqrt {3}\)
Gavish, M., & Donoho, D. L. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2323359 · Cited by 675
Euclidean Distance Matrices: Essential theory, algorithms, and applications
Dokmanic, I., Parhizkar, R., Ranieri, J., & Vetterli, M. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2015.2398954 · Cited by 611
Candès, E. J., & Plan, Y. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2111771 · Cited by 569
A Novel Sparse Compositional Technique Reveals Microbial Perturbations
Martino, C., Morton, J. T., Marotz, C. A., Thompson, L. R., Tripathi, A., Knight, R., & Zengler, K. (2019) · mSystems · doi:10.1128/msystems.00016-19 · Cited by 556
Low-Rank Matrix Completion by Riemannian Optimization
Vandereycken, B. (2013) · SIAM Journal on Optimization · doi:10.1137/110845768 · Cited by 491
Hankel Matrix Rank Minimization with Applications to System Identification and Realization
Fazel, M., Pong, T. K., Sun, D., & Tseng, P. (2013) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/110853996 · Cited by 487
Matrix estimation by Universal Singular Value Thresholding
Chatterjee, S. (2015) · The Annals of Statistics · doi:10.1214/14-aos1272 · Cited by 465
52nd IEEE Conference on Decision and Control
(2013) · doi:10.1109/cdc20427.2013 · Cited by 452
Statistical physics of inference: thresholds and algorithms
Zdeborová, L., & Krzakala, F. (2016) · Advances in Physics · doi:10.1080/00018732.2016.1211393 · Cited by 440
An Overview of Low-Rank Matrix Recovery From Incomplete Observations
Davenport, M. A., & Romberg, J. (2016) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2016.2539100 · Cited by 439
A tensor-based method for missing traffic data completion
Tan, H., Feng, G., Feng, J., Wang, W., Zhang, Y.-J., & Li, F. (2013) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2012.12.007 · Cited by 427
Blind Deconvolution Using Convex Programming
Ahmed, A., Recht, B., & Romberg, J. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2294644 · Cited by 387
Statistical guarantees for the EM algorithm: From population to sample-based analysis
Balakrishnan, S., Wainwright, M. J., & Yu, B. (2017) · The Annals of Statistics · doi:10.1214/16-aos1435 · Cited by 384
Training and testing of recommender systems on data missing not at random
Steck, H. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835895 · Cited by 365
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
Online identification and tracking of subspaces from highly incomplete information
Balzano, L., Nowak, R., & Recht, B. (2010) · 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2010.5706976 · Cited by 331
Solving Systems of Random Quadratic Equations via Truncated Amplitude Flow
Wang, G., Giannakis, G. B., & Eldar, Y. C. (2018) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2756858 · Cited by 330
Guaranteed Matrix Completion via Non-Convex Factorization
Sun, R., & Luo, Z.-Q. (2016) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2598574 · Cited by 309
Parallel stochastic gradient algorithms for large-scale matrix completion
Recht, B., & Ré, C. (2013) · Mathematical Programming Computation · doi:10.1007/s12532-013-0053-8 · Cited by 300
Bilinear Generalized Approximate Message Passing—Part I: Derivation
Parker, J. T., Schniter, P., & Cevher, V. (2014) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2014.2357776 · Cited by 281
Zero-preserving imputation of single-cell RNA-seq data
Linderman, G. C., Zhao, J., Roulis, M., Bielecki, P., Flavell, R. A., Nadler, B., & Kluger, Y. (2022) · Nature Communications · doi:10.1038/s41467-021-27729-z · Cited by 275
ADMiRA: Atomic Decomposition for Minimum Rank Approximation
Lee, K., & Bresler, Y. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2054251 · Cited by 267
Multi-View Learning With Incomplete Views
Xu, C., Tao, D., & Xu, C. (2015) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2490539 · Cited by 260
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
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
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
Metadata
- Authors
- Keshavan, R. H., Oh, S., & Montanari, A.
- Venue
- 2009 IEEE International Symposium on Information Theory
- Publisher
- IEEE
- Published
- 2009-06
- Pages
- 324-328
- OpenAlex
- W2000157792
- Cited by
- 650
- References
- 25
- FWCI
- 81.70
- 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.