The DOI matches its Crossref record; 63 of the 63 references it cites were found in a registry or an index.
Guaranteed Matrix Completion via Non-Convex Factorization
Open accessAbstract
Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis.
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
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Matrix Factorization Techniques for Recommender Systems
Koren, Y., Bell, R., & Volinsky, C. (2009) · Computer · doi:10.1109/mc.2009.263 · Cited by 11,673
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
Exact 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
Weik, M. H. (2000) · Computer Science and Communications Dictionary · doi:10.1007/1-4020-0613-6_12436 · Cited by 2,570
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
Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization
Tseng, P. (2001) · Journal of Optimization Theory and Applications · doi:10.1023/a:1017501703105 · Cited by 1,989
Candes, E. J., & Plan, Y. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2035722 · Cited by 1,709
A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization
Razaviyayn, M., Hong, M., & Luo, Z.-Q. (2013) · SIAM Journal on Optimization · doi:10.1137/120891009 · Cited by 1,304
Self-citationEfficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems
Nesterov, Y. (2012) · SIAM Journal on Optimization · doi:10.1137/100802001 · Cited by 1,187
Quantum State Tomography via Compressed Sensing
Gross, D., Liu, Y.-K., Flammia, S. T., Becker, S., & Eisert, J. (2010) · Physical Review Letters · doi:10.1103/physrevlett.105.150401 · Cited by 1,093
Phase Retrieval via Wirtinger Flow: Theory and Algorithms
Candès, E. J., Li, X., & Soltanolkotabi, M. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2399924 · Cited by 1,049
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
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
Toh, K.-C., & Yun, S. (2009) · National University of Singapore · Cited by 923
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
Large-Scale Parallel Collaborative Filtering for the Netflix Prize
Zhou, Y., Wilkinson, D., Schreiber, R., & Pan, R. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-68880-8_32 · Cited by 700
On the convergence of the block nonlinear Gauss–Seidel method under convex constraints
Grippo, L., & Sciandrone, M. (2000) · Operations Research Letters · doi:10.1016/s0167-6377(99)00074-7 · Cited by 678
A Simpler Approach to Matrix Completion
Recht, B. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0910.0651 · Cited by 673
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
Recovering Low-Rank Matrices From Few Coefficients in Any Basis
Gross, D. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2104999 · Cited by 602
Large-scale matrix factorization with distributed stochastic gradient descent
Gemulla, R., Nijkamp, E., Haas, P. J., & Sismanis, Y. (2011) · Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2020408.2020426 · Cited by 589
Recovering low-rank matrices from few coefficients in any basisPreprint
Gross, D. (2010) · Cited by 576
Phase Retrieval Using Alternating Minimization
Netrapalli, P., Jain, P., & Sanghavi, S. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2448516 · Cited by 535
Non-Linear Programming Via Penalty Functions
Zangwill, W. I. (1967) · Management Science · doi:10.1287/mnsc.13.5.344 · Cited by 511
Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
Liu, Z., & Vandenberghe, L. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090755436 · Cited by 490
Perturbation bounds in connection with singular value decomposition
Wedin, P.-Å. (1972) · BIT · doi:10.1007/bf01932678 · Cited by 460
Gradient Convergence in Gradient methods with Errors
Bertsekas, D. P., & Tsitsiklis, J. N. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497331063 · Cited by 437
Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
Negahban, S. N., & Wainwright, M. J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.2118 · Cited by 402
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
Strong oracle optimality of folded concave penalized estimation
Fan, J., Xue, L., & Zou, H. (2014) · The Annals of Statistics · doi:10.1214/13-aos1198 · Cited by 313
A Simpler Approach to Matrix Completion
RechtBenjamin (2011) · Journal of Machine Learning Research · doi:10.5555/1953048.2185803 · Cited by 310
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
A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems
Zhang, C.-H., & Zhang, T. (2012) · Statistical Science · doi:10.1214/12-sts399 · Cited by 296
Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares
Hastie, T. J., Mazumder, R., Lee, J. D., & Zadeh, R. B. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1410.2596 · Cited by 291
Hong, M., Sun, R., Baligh, H., & Luo, Z.-Q. (2013) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2013.130211 · Cited by 271
Self-citationScalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems
Yu, H.-F., Hsieh, C.-J., Si, S., & Dhillon, I. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.168 · Cited by 253
Truncated Power Method for Sparse Eigenvalue Problems
Yuan, X., & Zhang, T. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1112.2679 · Cited by 238
Spectral techniques applied to sparse random graphs
Feige, U., & Ofek, E. (2005) · Random Structures & Algorithms · doi:10.1002/rsa.20089 · Cited by 221
Perturbation theory for the singular value decomposition
Stewart, G. W. (1990) · University Libraries (University of Maryland) · Cited by 217
Understanding Alternating Minimization for Matrix Completion
Hardt, M. (2014) · 2014 IEEE 55th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.75 · Cited by 216
Fast global convergence of gradient methods for high-dimensional statistical recovery
Agarwal, A., Negahban, S., & Wainwright, M. J. (2012) · The Annals of Statistics · doi:10.1214/12-aos1032 · Cited by 204
Non-convex Robust PCAPreprint
Netrapalli, P., Niranjan, U. N., Sanghavi, S., Anandkumar, A., & Jain, P. (2014) · CaltechAUTHORS (California Institute of Technology) · doi:10.48550/arxiv.1410.7660 · Cited by 177
Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima
Loh, P., & Wainwright, M. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1305.2436 · Cited by 169
Fast als-based matrix factorization for explicit and implicit feedback datasets
Pilászy, I., Zibriczky, D., & Tikk, D. (2010) · Proceedings of the fourth ACM conference on Recommender systems · doi:10.1145/1864708.1864726 · Cited by 166
A fast parallel SGD for matrix factorization in shared memory systems
Zhuang, Y., Chin, W.-S., Juan, Y.-C., & Lin, C. (2013) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/2507157.2507164 · Cited by 165
Major components of the gravity recommendation system
Takács, G., Pilászy, I., Németh, B., & Tikk, D. (2007) · ACM SIGKDD Explorations Newsletter · doi:10.1145/1345448.1345466 · Cited by 156
Recovering the missing components in a large noisy low-rank matrix: application to SFM
Chen, P., & Suter, D. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.52 · Cited by 154
A Unified View of Matrix Factorization Models
Singh, A. P., & Gordon, G. J. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87481-2_24 · Cited by 150
Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix ProblemsPreprint
De, C., Olukotun, K., & Ré, C. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.1134 · Cited by 107
Truncated power method for sparse eigenvalue problems
YuanXiao-Tong, & ZhangTong (2013) · Journal of Machine Learning Research · doi:10.5555/2567709.2502610 · Cited by 104
Fast matrix completion without the condition numberPreprint
Hardt, M., & Wootters, M. K. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1407.4070 · Cited by 84
Universal Matrix CompletionPreprint
Bhojanapalli, S., & Jain, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.2324 · Cited by 67
Cross-Layer Provision of Future Cellular Networks: A WMMSE-based approach
Baligh, H., Hong, M., Liao, W.-C., Luo, Z.-Q. T., Razaviyayn, M., Sanjabi, M., & Sun, R. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2335237 · Cited by 46
Self-citationWorst-case complexity of cyclic coordinate descent: $$O(n^2)$$ gap with randomized version
Sun, R., & Ye, Y. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01437-5 · Cited by 45
Self-citationEfficient algorithms for collaborative filtering
Keshavan, R. H. (2012) · Cited by 41
On the Efficiency of Random Permutation for ADMM and Coordinate Descent
Sun, R., Luo, Z.-Q. T., & Ye, Y. (2019) · Mathematics of Operations Research · doi:10.1287/moor.2019.0990 · Cited by 36
Self-citationImproved Iteration Complexity Bounds of Cyclic Block Coordinate Descent for Convex ProblemsPreprint
Sun, R., & Hong, M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.04680 · Cited by 33
Self-citationNonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial TimePreprint
Wang, Z., Lu, H., & Liu, H. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1408.5352 · Cited by 32
On the Expected Convergence of Randomly Permuted ADMMPreprint
Sun, R., Luo, Z.-Q. T., & Ye, Y. (2015) · arXiv (Cornell University) · Cited by 31
Self-citationFast Exact Matrix Completion with Finite SamplesPreprint
Jain, P., & Netrapalli, P. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1411.1087 · Cited by 10
Matrix Completion via Nonconvex Factorization: Algorithms and Theory
Sun, R. (2015) · University of Minnesota Digital Conservancy (University of Minnesota) · Cited by 8
Self-citation
Cited by
Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems
Chen, Y., & Candès, E. J. (2017) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.21638 · Cited by 477
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
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
A review on distance based time series classification
Abanda, A., Mori, U., & Lozano, J. A. (2019) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-018-0596-4 · Cited by 296
Metadata
- Authors
- Sun, R., & Luo, Z.-Q.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2016-11
- Volume
- 62
- Issue
- 11
- Pages
- 6535-6579
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2566608758
- Cited by
- 309
- References
- 63
- FWCI
- 37.71
- 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.