Enhancing matrix completion using a modified second-order total variation. (English) Zbl 1417.90159

Summary: In this paper, we propose a new method to deal with the matrix completion problem. Different from most existing matrix completion methods that only pursue the low rank of underlying matrices, the proposed method simultaneously optimizes their low rank and smoothness such that they mutually help each other and hence yield a better performance. In particular, the proposed method becomes very competitive with the introduction of a modified second-order total variation, even when it is compared with some recently emerged matrix completion methods that also combine the low rank and smoothness priors of matrices together. An efficient algorithm is developed to solve the induced optimization problem. The extensive experiments further confirm the superior performance of the proposed method over many state-of-the-art methods.


90C90 Applications of mathematical programming
65F30 Other matrix algorithms (MSC2010)
15A83 Matrix completion problems


Full Text: DOI


[1] Komodakis, N., Image Completion Using Global Optimization, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Volume 1 (CVPR’06)
[2] Koren, Y.; Bell, R.; Volinsky, C., Matrix factorization techniques for recommender systems, The Computer Journal, 42, 8, 30-37 (2009)
[3] Ji, H.; Liu, C.; Shen, Z.; Xu, Y., Robust video denoising using low rank matrix completion, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR ’10)
[4] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Foundations of Computational Mathematics, 9, 6, 717-772 (2009) · Zbl 1219.90124
[5] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52, 3, 471-501 (2010) · Zbl 1198.90321
[6] Chen, Y., Incoherence-optimal matrix completion, Institute of Electrical and Electronics Engineers Transactions on Information Theory, 61, 5, 2909-2923 (2015) · Zbl 1359.15022
[7] Liu, G.; Li, P., Low-rank matrix completion in the presence of high coherence, IEEE Transactions on Signal Processing, 64, 21, 5623-5633 (2016) · Zbl 1414.94363
[8] Ji, S. W.; Ye, J. P., An accelerated gradient method for trace norm minimization, Proceedings of the 26th Annual International Conference on Machine Learning (ICML ’09), ACM
[9] Toh, K.-C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific Journal of Optimization, 6, 3, 615-640 (2010) · Zbl 1205.90218
[10] Fornasier, M.; Rauhut, H.; Ward, R., Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM Journal on Optimization, 21, 4, 1614-1640 (2011) · Zbl 1236.65044
[11] Cai, J.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20, 4, 1956-1982 (2010) · Zbl 1201.90155
[12] Cai, J.-F.; Osher, S., Fast singular value thresholding without singular value decomposition, Methods and Applications of Analysis, 20, 4, 335-351 (2013) · Zbl 1401.65042
[13] Xu, C.; Lin, Z. C.; Zha, H. B., A unified convex surrogate for the Schatten-p norm, Proceedings of the AAAI Conference on Artificial Intelligence
[14] Foucart, S.; Rauhut, H., A Mathematical Introduction to Compressive Sensing (2013), Berlin, Heidelberg, Germany: Springer, Berlin, Heidelberg, Germany · Zbl 1315.94002
[15] Chartrand, R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14, 10, 707-710 (2007)
[16] Wen, J.; Li, D.; Zhu, F., Stable recovery of sparse signals via \(L_p\)-minimization, Applied and Computational Harmonic Analysis, 38, 1, 161-176 (2015) · Zbl 1345.94020
[17] Wang, Y.; Yin, W., Sparse signal reconstruction via iterative support detection, SIAM Journal on Imaging Sciences, 3, 3, 462-491 (2010) · Zbl 1206.68340
[18] Yin, P.; Lou, Y.; He, Q.; Xin, J., Minimization of \(l_{1-2}\) for compressed sensing, SIAM Journal on Scientific Computing, 37, 1, A536-A563 (2015) · Zbl 1316.90037
[19] Wang, W.; Wang, J.; Zhang, Z., Robust Signal Recovery with Highly Coherent Measurement Matrices, IEEE Signal Processing Letters, 24, 3, 304-308 (2017)
[20] Marjanovic, G.; Solo, V., On \(l_q\) optimization and matrix completion, IEEE Transactions on Signal Processing, 60, 11, 5714-5724 (2012) · Zbl 1393.94353
[21] Hu, Y.; Zhang, D.; Ye, J.; Li, X.; He, X., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Transactions on Pattern Analysis and Machine Intelligence, 35, 9, 2117-2130 (2013)
[22] Ma, T.-H.; Lou, Y.; Huang, T.-Z., Truncated \(L_{1-2}\) models for sparse recovery and rank minimization, SIAM Journal on Imaging Sciences, 10, 3, 1346-1380 (2017) · Zbl 1397.94021
[23] Nie, F. P.; Huang, H.; Ding, C., Low-rank matrix recovery via efficient Schatten p-norm minimization, Proceedings of the 26th AAAI Conference on Artificial Intelligence
[24] Lai, M. J.; Xu, Y. Y.; Yin, W. T., Improved iteratively reweighted least squares for unconstrained smoothed \(l_q\) minimization, SIAM Journal on Numerical Analysis, 51, 2, 927-957 (2013) · Zbl 1268.49038
[25] Cao, F.; Chen, J.; Ye, H.; Zhao, J.; Zhou, Z., Recovering low-rank and sparse matrix based on the truncated nuclear norm, Neural Networks, 85, 10-20 (2017) · Zbl 1428.68231
[26] Oh, T.-H.; Tai, Y.-W.; Bazin, J.-C.; Kim, H.; Kweon, I. S., Partial sum minimization of singular values in robust PCA: Algorithm and applications, IEEE Transactions on Pattern Analysis and Machine Intelligence, 38, 4, 744-758 (2016)
[27] Keshavan, R. H.; Montanari, A.; Oh, S., Matrix completion from a few entries, IEEE Transactions on Information Theory, 56, 6, 2980-2998 (2010) · Zbl 1366.62111
[28] Wen, Z.; Yin, W.; Zhang, Y., Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Mathematical Programming Computation, 4, 4, 333-361 (2012) · Zbl 1271.65083
[29] Lee, K.; Bresler, Y., ADMiRA: atomic decomposition for minimum rank approximation, IEEE Transactions on Information Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[30] Wang, Z.; Lai, M.-J.; Lu, Z.; Fan, W.; Davulcu, H.; Ye, J., Orthogonal rank-one matrix pursuit for low rank matrix completion, SIAM Journal on Scientific Computing, 37, 1, A488-A514 (2015) · Zbl 1315.65044
[31] Davenport, M. A.; Romberg, J., An overview of low-rank matrix recovery from incomplete observations, IEEE Journal of Selected Topics in Signal Processing, 10, 4, 608-622 (2016)
[32] Rodriguez, P., Total variation regularization algorithms for images corrupted with different noise models: a review, Journal of Electrical and Computer Engineering, 2013 (2013)
[33] Han, Xu; Wu, Jiasong; Wang, Lu; Chen, Yang; Senhadji, Lotf; Shu, Huazhong, Linear total variation approximate regularized nuclear norm optimization for matrix completion, Abstract and Applied Analysis, 2014 (2014) · Zbl 1474.94042
[34] Chen, Y.-L.; Hsu, C.-T.; Liao, H.-Y. M., Simultaneous tensor decomposition and completion using factor priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, 36, 3, 577-591 (2014)
[35] Yokota, T.; Zhao, Q.; Cichocki, A., Smooth PARAFAC decomposition for tensor completion, IEEE Transactions on Signal Processing, 64, 20, 5423-5436 (2016) · Zbl 1414.94716
[36] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Review, 51, 3, 455-500 (2009) · Zbl 1173.65029
[37] Papafitsoros, K.; Schoenlieb, C. B.; Sengul, B., Combined first and second order total variation inpainting using split Bregman, Image Processing On Line, 3, 112-136 (2013)
[38] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3, 1, 1-122 (2011) · Zbl 1229.90122
[39] Benner, P.; Li, R.-C.; Truhar, N., On the ADI method for Sylvester equations, Journal of Computational and Applied Mathematics, 233, 4, 1035-1045 (2009) · Zbl 1176.65050
[40] Lin, Z. C.; Liu, R. S.; Su, Z. X., Linearized alternating direction method with adaptive penalty for low-rank representation, Proceedings of the 25th Annual Conference on Neural Information Processing Systems
[41] Wang, Z.; Bovik, A. C.; Sheikh, H. R.; Simoncelli, E. P., Image quality assessment: from error visibility to structural similarity, IEEE Transactions on Image Processing, 13, 4, 600-612 (2004)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.