A non-convex algorithm framework based on DC programming and DCA for matrix completion. (English) Zbl 1312.65093

Summary: Matrix completion aims to recover an unknown low-rank or approximately low-rank matrix from a sampling set of its entries. It is shown that this problem can be solved via its tightest convex relaxation obtained by minimizing the nuclear norm instead of the rank function. Recent studies have also shown that some non-convex penalties like \(M_p\) minimization and weighted nuclear norm minimization algorithms are able to recover low-rank matrix in a more efficient way. In this paper, we propose a unified framework based on difference of convex functions (DC) programming and DC algorithms (DCA), by which \(M_p\) minimization and weighted nuclear norm minimization algorithms can be obtained as special cases of the general framework. In addition, we give another non-convex penalty – exponential type penalty. We make some comparison between numerical tests of our algorithms and the state-of-the-art method APGL and NIHT on randomly generated matrices and real matrix completion problems, the results suggest that our methods are more effective and promising. Moreover, for the application on low-rank image recovery, these non-convex algorithms we proposed also perform well and the results are more satisfactory and reasonable.


65K05 Numerical mathematical programming methods
65F30 Other matrix algorithms (MSC2010)
90C26 Nonconvex programming, global optimization
15A83 Matrix completion problems
Full Text: DOI


[1] An, L.T.H., Tao, P.D.: Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J Global Optim. 11, 253-285 (1997) · Zbl 0905.90131
[2] An, L.T.H., Tao, P.D.: DC programming: theory, algorithms and applications: the state of the art. In: First International Workshop on Global Constrained Optimization and Constraint Satisfaction (Cocos’ 02), 28 p., pp. 2-4. Valbonne-Sophia Antipolis, France (2002)
[3] An, L.T.H., Tao, P.D.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23-46 (2005) · Zbl 1116.90122
[4] Biswas, P., Liang, T.C., Ye, Y.Y.: Semidefinite programming based algorithms for sensor network localization. ACM Trans. Sensor Netw. 2(2), 188-220 (2006)
[5] Cai, J.F., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim 20(4), 1956-1982 (2010) · Zbl 1201.90155
[6] Candès, E.J., Wakin, M.B., Boyd, S.P.: Enhancing sparsity by reweighted ℓ1 minimization. J. Fourier Anal. Appl. 14, 877-905 (2008) · Zbl 1176.94014
[7] Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9(6), 717-772 (2009) · Zbl 1219.90124
[8] Chen, P., Suter, D.: Recovering the missing components in a large noisy low rank matrix: application to SMF. IEEE Trans. Pattern Anal. Mach. Intell. 26(8), 1051-1063 (2004)
[9] Chistov, A.L., Grigoriev, D.Y.: Complexity of quantifier elimination in the theory of algebraically closed fields. Mathematical Foundations of Computer Science, vol. 176, pp 17-31. Springer Verlag (1984)
[10] Elad, M., Aharon, M.: Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans. Image Process. 15(12), 3736-3745 (2006)
[11] Fazel, M.: Matrix rank minimization with applications. PhD thesis. Stanford University (2002) · Zbl 1268.49038
[12] Fazel, M., Hindi, H., Boyd, S.P.: Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. Am. Control. Conf. 3, 2156-2162 (2003)
[13] Foucart, S., Lai, M.J.: Sparsest solutions of undertermined linear systems via ℓp-minimization for 0<q≤1. Appl. Comput. Harmon. Anal. 26(3), 395-407 (2009) · Zbl 1171.90014
[14] Gasso, G., Rakotomamonjy, A., Canu, S.: Recovering sparse signals with a certain family of nonconvex penalties and DC programming. IEEE Trans. Sig. Process. 57(12), 4686-4698 (2009) · Zbl 1391.90489
[15] Gaïffas, S., Lecué, G.: :Weighted algorithms for compressed sensing and matrix completion. arXiv:preprint, arXiv:1107.1638. (2011) · Zbl 1365.62137
[16] Geng, J., Wang, L.S., Fu, A.M.: A majorization-minimization weighted soft thresholding algorithm for weighted nuclear norm minimization. Inernational J Meachine Learn. Cybern. (2014) · Zbl 1366.94112
[17] Goldberg, K., Roeder, T., Gupta, D., Perkins, C.: Eigentaste: A constant time collaborative filtering algorithm. Inf. Retr. 4(2), 133-151 (2001) · Zbl 0989.68052
[18] Goldfarb, D., Ma, S.Q., Wen, Z.W.: Solving low-rank matrix completion problems efficiently. In: 47th Annual Allerton Conference on Communication, Control, and Computing, pp. 1013-1020. Illinois (2009) · Zbl 1171.90014
[19] Hiriart Urruty, J.B., Lemarechal, C.: Convex analysis and minimization algorithms: fundamentals. Springer Verlag (1996) · Zbl 0795.49001
[20] Horst, R., Thoai, N.V.: DC programming: overview. J Optim. Theory andAppl. 103(1), 1-43 (1999) · Zbl 1073.90537
[21] Ji, H., Liu, C.Q., Shen, Z.W., Xu, Y.H.: Robust video denoising using low rank matrix completion. In: 2010 IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), pp. 1791-1798 (2010)
[22] Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56(6), 2980-2998 (2010) · Zbl 1366.62111
[23] Kong, L.C., Xiu, N.H.: Exact low-rank matrix recovery via nonconvex schatten p-minimization. Asia-Pac. J. Oper. Reasearch 30(3) (2013) · Zbl 1273.90257
[24] Lai, M.J., Xu, Y.Y., Yin, W.T.: Improved iteratively reweighted least squares for unconstrained smoothed ℓq minimization. SIAM J. Numer. Anal. 51(2), 927-957 (2013) · Zbl 1268.49038
[25] Lai, M.J., Wang, J.Y.: An unconstrainted ℓq minimization with 0<q≤1 for sparse solution of underdetermined linear systems. SIAM J. Optim. 21(1), 82-101 (2010) · Zbl 1220.65051
[26] Lee, K., Bresler, Y.: Admira: atomic decomposition for minimum rank approximation. IEEE Trans. Inf. Theory 56(9), 4402-4416 (2010) · Zbl 1366.94112
[27] Lewis, A.S.: The convex analysis of unitarily invariant matrix norms. J. Convex Analysis 2, 173-183 (1995) · Zbl 0860.15026
[28] Lin, Z.C., Chen, M.M., Ma, Y.: The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices. arXiv:preprint, arXiv:1009.5055. (2010) · Zbl 1268.49038
[29] Liu, Y.J., Sun, D.F., Toh, K.C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Program. 133(1-2), 399-436 (2012) · Zbl 1262.90125
[30] Meka, R., Jain, P., Dhillon, I.S.: Guaranteed rank minimization via singular value projection. Adv. Neural Inf. Process. Syst., 937-945 (2010) · Zbl 0973.90526
[31] Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim. Methods Softw. 11, 625-653 (1999) · Zbl 0973.90526
[32] Tanner, J., Wei, K.: Normalized iterative hard thresholding for matrix completion. Proceedings available online at http://people.maths.ox.ac.uk/tanner/papers/TaWei_NIHT.pdf. (2013) · Zbl 1282.65043
[33] Tao, P.D., An, L.T.H.: Convex analysis approach to d.c. programming: Theory, Algorithms and Applications. Acta Mathematica Vietnamica, (dedicated to Professor Hoang Tuy on the occasion of his 70th birthday), vol. 22, pp. 289-355 (1997) · Zbl 0895.90152
[34] Tao, P.D., An, L.T.H.: A d.c. optimization algorithms for solving the trust region subproblem. SIAM J. Optim. 8(2), 476-505 (1998) · Zbl 0913.65054
[35] Toh, K.C., Yun, S.W.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615-640 (2010) · Zbl 1205.90218
[36] Ttnc, R.H., Toh, K.C., Todd, M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. 95(2), 189-217 (2003) · Zbl 1030.90082
[37] Xu, J.: Reweighted Nuclear Norm Minimization for Matrix Completion. Proceedings available online at https://webspace.utexas.edu/jx598/www/Reweighted.pdf. (2011)
[38] Wang, M., Hua, X.S., Hong, R.C., Tang, J.H., Qi, G., Song, Y.: Unified video annotation via multigraph learning. IEEE Trans. Circ. Syst. Video Technol. 19(5), 733-746 (2009)
[39] Wang, M., Hua, X.S., Tang, J.H., Hong, R.C.: Beyond distance measurement: Constructing neighborhood similarity for video annotation. IEEE Trans. Multimed. 11(3), 465-476 (2009)
[40] Wang, X., Wang, S., Bi, D.W.: Distributed visual-target-surveillance system in wireless sensor networks. IEEE Trans. Syst. Man Cybern. Part B, Cybern. 39(5), 1134-1146 (2009)
[41] Wen, Z.W., Yin, W.T., Zhang, Y.: Solving a low-rank factorization model for matrix completion by nonlinear successive over-relaxation algorithm. Math. Program. Comput. 4(4), 333-361 (2012) · Zbl 1271.65083
[42] Zeng, B., Fu, J.J.: Directional discrete cosine transforms-a new framework for image coding. IEEE Trans. Circ. Syst. Circ. Syst. Video Technol. 18(3), 305-313 (2008)
[43] Zhu, G., Yan, S., Ma, Y.: Image tag refinement towards low-rank, content-tag prior and error sparsity. Proceedings of the international conference on Multimedia. ACM, 461-470 (2010)
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.