The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization
Open accessAbstract
Recovering a large matrix from a small subset of its entries is a challenging problem arising in many real applications, such as image inpainting and recommender systems. Many existing approaches formulate this problem as a general low-rank matrix approximation problem. Since the rank operator is nonconvex and discontinuous, most of the recent theoretical studies use the nuclear norm as a convex relaxation. One major limitation of the existing approaches based on nuclear norm minimization is that all the singular values are simultaneously minimized, and thus the rank may not be well approximated in practice. In this paper, we propose to achieve a better approximation to the rank of matrix by truncated nuclear norm, which is given by the nuclear norm subtracted by the sum of the largest few singular values. In addition, we develop a novel matrix completion algorithm by minimizing the Truncated Nuclear Norm. We further develop three efficient iterative procedures, TNNR-ADMM, TNNR-APGL, and TNNR-ADMMAP, to solve the optimization problem. TNNR-ADMM utilizes the alternating direction method of multipliers (ADMM), while TNNR-AGPL applies the accelerated proximal gradient line search method (APGL) for the final optimization. For TNNR-ADMMAP, we make use of an adaptive penalty according to a novel update rule for ADMM to achieve a faster convergence rate. Our empirical study shows encouraging results of the proposed algorithms in comparison to the state-of-the-art matrix completion algorithms on both synthetic and real visual datasets.
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., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
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
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
Factorization meets the neighborhood: a multifaceted collaborative filtering model
Koren, Y. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401944 · Cited by 3,852
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
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
Self-citationThe 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
Wright, J. N., Ganesh, A., Rao, S., Peng, Y., & Ma, Y. (2009) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1,495
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
Linearized Alternating Direction Method with Adaptive Penalty for Low-Rank Representation
Lin, Z., Liu, R., & Su, Z. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.0367 · Cited by 992
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
Maximum-Margin Matrix Factorization
Srebro, N., Rennie, J. D. M., & Jaakkola, T. (2004) · Cited by 962
A rank minimization heuristic with application to minimum order system approximation
Fazel, M., Hindi, H., & Boyd, S. P. (2001) · Proceedings of the 2001 American Control Conference. (Cat. No.01CH37148) · doi:10.1109/acc.2001.945730 · Cited by 956
Fast maximum margin matrix factorization for collaborative prediction
Rennie, J. D. M., & Srebro, N. (2005) · Proceedings of the 22nd international conference on Machine learning - ICML '05 · doi:10.1145/1102351.1102441 · Cited by 939
Toh, K.-C., & Yun, S. (2009) · National University of Singapore · Cited by 923
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
RASL: Robust Alignment by Sparse and Low-Rank Decomposition for Linearly Correlated Images
Peng, Y., Ganesh, A., Wright, J., Xu, W., & Ma, Y. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.282 · Cited by 817
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
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
Self-citationRobust video denoising using low rank matrix completion
Ji, H., Liu, C., Shen, Z., & Xu, Y. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5539849 · Cited by 483
He, B. S., Yang, H., & Wang, S. L. (2000) · Journal of Optimization Theory and Applications · doi:10.1023/a:1004603514434 · Cited by 465
Scalable Collaborative Filtering Approaches for Large Recommender Systems
Takács, G., Pilászy, I., Németh, B., & Tikk, D. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577091 · Cited by 464
Recovering Low-Rank and Sparse Components of Matrices from Incomplete and Noisy Observations
Tao, M., & Yuan, X. (2011) · SIAM Journal on Optimization · doi:10.1137/100781894 · Cited by 453
Guaranteed Rank Minimization via Singular Value Projection
Jain, P., Meka, R., & Dhillon, I. S. (2010) · Cited by 420
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
Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming
He, B., Tao, M., & Yuan, X. (2012) · SIAM Journal on Optimization · doi:10.1137/110822347 · Cited by 360
Local Minima and Convergence in Low-Rank Semidefinite Programming
Burer, S., & Monteiro, R. D. C. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0564-1 · Cited by 347
A Simpler Approach to Matrix Completion
RechtBenjamin (2011) · Journal of Machine Learning Research · doi:10.5555/1953048.2185803 · Cited by 310
Image Completion Using Global Optimization
Komodakis, N. (2006) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2006.141 · Cited by 273
Trace Norm Regularization: Reformulations, Algorithms, and Multi-Task Learning
Pong, T. K., Tseng, P., Ji, S., & Ye, J. (2010) · SIAM Journal on Optimization · doi:10.1137/090763184 · Cited by 208
Self-citationEriksson, A., & van den Hengel, A. (2010) · 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2010.5540139 · Cited by 190
Principal component analysis with missing data and its application to polyhedral object modeling
Shum, H.-Y., Ikeuchi, K., & Reddy, R. (1995) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.406651 · Cited by 188
Transduction with Matrix Completion: Three Birds with One Stone
Goldberg, A. B., Recht, B., Xu, J., Nowak, R. D., & Zhu, X. (2010) · Cited by 188
Matrix completion by Truncated Nuclear Norm Regularization
Zhang, D., Hu, Y., Ye, J., Li, X., & He, X. (2012) · 2012 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2012.6247927 · Cited by 160
Self-citationCollaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
Srebro, N., & Salakhutdinov, R. (2010) · neural information processing systems · Cited by 158
Matrix Completion for Multi-label Image Classification
Cabral, R., la Torre, F. D., Costeira, J. P., & Bernardino, A. J. M. (2011) · Cited by 147
Learning with the Weighted Trace-norm under Arbitrary Sampling DistributionsPreprint
Foygel, R., Salakhutdinov, R., Shamir, O., & Srebro, N. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1106.4251 · Cited by 49
Spatiotemporal inpainting for recovering texture maps of partially occluded building facades
Rasmussen, C. E., & Korah, T. (2005) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2005.1530344 · Cited by 23
Cited by
Semantic Image Inpainting with Deep Generative Models
Yeh, R. A., Chen, C., Lim, T. Y., Schwing, A. G., Hasegawa-Johnson, M., & Do, M. N. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.728 · Cited by 1,206
Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm
Lu, C., Tang, J., Yan, S., & Lin, Z. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2511584 · Cited by 307
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
Metadata
- Authors
- Hu, Y., Zhang, D., Ye, J., Li, X., & He, X.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2013-09
- Volume
- 35
- Issue
- 9
- Pages
- 2117-2130
- ISSN
- 0162-8828 (ISSN-L)
- 2160-9292
- OpenAlex
- W1969698720
- Cited by
- 829
- References
- 42
- FWCI
- 34.39
- 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.
