Low-rank matrix recovery with Ky Fan 2-\(k\)-norm. (English) Zbl 1490.90219

Summary: Low-rank matrix recovery problem is difficult due to its non-convex properties and it is usually solved using convex relaxation approaches. In this paper, we formulate the non-convex low-rank matrix recovery problem exactly using novel Ky Fan 2-\(k\)-norm-based models. A general difference of convex functions algorithm (DCA) is developed to solve these models. A proximal point algorithm (PPA) framework is proposed to solve sub-problems within the DCA, which allows us to handle large instances. Numerical results show that the proposed models achieve high recoverability rates as compared to the truncated nuclear norm method and the alternating bilinear optimization approach. The results also demonstrate that the proposed DCA with the PPA framework is efficient in handling larger instances.


90C25 Convex programming
90C90 Applications of mathematical programming


Full Text: DOI arXiv


[1] Argyriou, A., Foygel, R., Srebro, N.: Sparse prediction with the \(k\)-support norm. In: NIPS, pp. 1466-1474. (2012)
[2] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., 1, 183-202 (2009) · Zbl 1175.94009
[3] Bhatia, R., Matrix Analysis, Graduate Texts in Mathematics (1997), New York: Springer-Verlag, New York
[4] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[5] Candès, EJ; Tao, T., Decoding by linear programming, IEEE Trans. Inform. Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121
[6] Doan, XV; Toh, KC; Vavasis, S., A proximal point algorithm for sequential feature extraction applications, SIAM J. Sci. Comput., 35, 1, A517-A540 (2013) · Zbl 1277.65044
[7] Doan, XV; Vavasis, S., Finding the largest low-rank clusters with Ky Fan \(2-k\)-norm and \(\ell_1\)-norm, SIAM J. Optim., 26, 1, 274-312 (2016) · Zbl 1332.15032
[8] Giraud, C., Low rank multivariate regression, Electron. J. Stat., 5, 775-799 (2011) · Zbl 1274.62434
[9] Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 2.0 beta. http://cvxr.com/cvx (2013)
[10] Hu, Y.; Zhang, D.; Ye, J.; Li, X.; He, X., Fast and accurate matrix completion via truncated nuclear norm regularization, IEEE Trans. Patt. Anal. Mach. Intell., 35, 9, 2117-2130 (2013)
[11] Hu, Z., Nie, F., Wang, R., Li, X.: Low rank regularization: a review. Neural Netw. (2020)
[12] Jacob, L.; Bach, F.; Vert, JP, Clustered multi-task learning: a convex formulation, NIPS, 21, 745-752 (2009)
[13] Jain, P., Netrapalli, P., Sanghavi, S.: Low-rank matrix completion using alternating minimization. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 665-674. ACM (2013) · Zbl 1293.65073
[14] Lee, K.; Bresler, Y., ADMiRA: atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory, 56, 9, 4402-4416 (2010) · Zbl 1366.94112
[15] Liu, YJ; Sun, D.; Toh, KC, An implementable proximal point algorithmic framework for nuclear norm minimization, Math. Program., 133, 1-2, 399-436 (2012) · Zbl 1262.90125
[16] Ma, TH; Lou, Y.; Huang, TZ, Truncated \(\ell_{1-2}\) models for sparse recovery and rank minimization, SIAM J. Imag. Sci., 10, 3, 1346-1380 (2017) · Zbl 1397.94021
[17] Mohan, K.; Fazel, M., Iterative reweighted algorithms for matrix rank minimization, J. Mach. Learn. Res., 13, 1, 3441-3473 (2012) · Zbl 1436.65055
[18] Nguyen, LT; Kim, J.; Shim, B., Low-rank matrix completion: a contemporary survey, IEEE Access, 7, 94215-94237 (2019)
[19] Pham-Dinh, T., Le-Thi, H.A.: Convex analysis approach to d.c. programming: theory, algorithms and applications. Acta Math. Viet. 22(1), 289-355 (1997) · Zbl 0895.90152
[20] Pham-Dinh, T.; Le-Thi, HA, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8, 2, 476-505 (1998) · Zbl 0913.65054
[21] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[22] Rockafellar, RT, Convex Analysis (1970), Princeton, NJ: Princeton University Press, Princeton, NJ · Zbl 0932.90001
[23] Toh, K.C., Todd, M.J., Tütüncü, R.H.: Sdpt3—a matlab software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1-4), 545-581 (1999) · Zbl 0997.90060
[24] Yin, P.; Esser, E.; Xin, J., Ratio and difference of \(\ell_1\) and \(\ell_2\) norms and sparse representation with coherent dictionaries, Commun. Inform. Syst., 14, 2, 87-109 (2014) · Zbl 1429.94037
[25] Yin, P.; Lou, Y.; He, Q.; Xin, J., Minimization of \(\ell_1-\ell_2\) for compressed sensing, SIAM J. Sci. Comput., 37, 1, A536-A563 (2015) · Zbl 1316.90037
[26] Ziȩtak, K., Subdifferentials, faces, and dual matrices, Linear Algeb. Appl., 185, 125-141 (1993) · Zbl 0772.15014
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.