A penalty decomposition method for rank minimization problem with affine constraints. (English) Zbl 1443.93011

Summary: The rank minimization problem with affine constraints is widely applied in the fields of control, system identification, and machine learning, and attracted much attention and well studied in the past few years. Unlike most of the existing methods where a nuclear norm is used to approximate the rank term, in this paper, we apply the penalty decomposition method to solve the rank minimization problem directly. One subproblem can be solved effectively by using linear conjugate gradient method, and the other one has closed-form solutions by taking full use of the problem’s favorable structure. Under some suitable assumptions, the convergence results for the proposed method are given. Finally, we do numerical experiments on randomly generated and real data, the results show that the proposed method is effective and promising.


93-10 Mathematical modeling or simulation for problems pertaining to systems and control theory
68T05 Learning and adaptive systems in artificial intelligence


Full Text: DOI


[1] Fazel, M.; Hindi, H.; Boyd, S. P., A rank minimization heuristic with application to minimum order system approximation, (Proceedings of the American Control Conference, 6 (2001), IEEE), 4734-4739
[2] Liu, Z.; Vandenberghe, L., Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl., 31, 1235-1256 (2009) · Zbl 1201.90151
[3] Rakotomamonjy, A.; Flamary, R.; Gasso, G.; Canu, S., Lp-Lq penalty for sparse linear and sparse multiple kernel multitask learning, IEEE Trans. Neural Netw., 22, 1307-1320 (2011)
[4] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Programming, 128, 321-353 (2011) · Zbl 1221.65146
[5] Cai, J. F.; Candès, E. J.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 1956-1982 (2010) · Zbl 1201.90155
[6] Hale, E. T.; Yin, W.; Zhang, Y., Fixed-point continuation for \(\ell_1\)-minimization: methodology and convergence, SIAM J. Optim., 19, 1107-1130 (2008) · Zbl 1180.65076
[7] Toh, K. C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific J. Optim., 6, 615-640 (2010) · Zbl 1205.90218
[8] Yang, J.; Yuan, X. M., Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Math. Comput., 82, 301-329 (2013) · Zbl 1263.90062
[9] Xiao, Y. H.; Jin, Z.-F., An alternating direction method for linear-constrained matrix nuclear norm minimization, Numer. Linear Algebra Appl., 19, 541-554 (2012) · Zbl 1274.65115
[10] Barzilai, J.; Borwein, J. M., Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055
[11] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2009) · Zbl 1219.90124
[12] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 471-501 (2010) · Zbl 1198.90321
[13] Zhou, S. L.; Xiu, N. H.; Luo, Z. Y., Sparse and low-rank covariance matrix estimation, J. Oper. Res. Soc. China, 1-20 (2014)
[14] Lee, K.; Bresler, Y., Admira: atomic decomposition for minimum rank approximation, IEEE Trans. Inf. Theory, 56, 4402-4416 (2010) · Zbl 1366.94112
[15] Jain, P.; Meka, R.; Dhillon, I. S., Guaranteed rank minimization via singular value projection, NIPS, 23, 937-945 (2010)
[16] Malek-Mohammadi, M.; Babaie-Zadeh, M.; Amini, A.; Jutten, C., Recovery of low rank matrices under affine constrain via a smoothed rank function, IEEE Trans. Signal Processing, 62, 981-992 (2014) · Zbl 1394.94363
[17] Lu, Z.; Zhang, Y., Penalty decomposition methods for rank minimization, Optim. Methods Softw., 1-28 (2014), [Epub ahead of print]
[18] Wen, Z.; Goldfarb, D.; Scheinberg, K., Block coordinate descent methods for semidefinite programming, Int. Ser. Oper. Res. Manage. Sci., 166, 533-564 (2012) · Zbl 1334.90118
[19] Lu, Z.; Zhang, Y., Sparse approximation via penalty decomposition methods, SIAM J. Optim., 23, 2448-2478 (2013) · Zbl 1295.90056
[20] Blumensath, T.; Davies, M. E., Iterative thresholding for sparse approximations, J. Fourier Anal. Appl., 14, 629-654 (2008) · Zbl 1175.94060
[21] Kelley, C. T., Iterative Methods for Linear and Nonlinear Equations (1995), SIAM: SIAM Philadelphia · Zbl 0832.65046
[23] Chen, C.; He, B.; Yuan, X., Matrix completion via an alternating direction method, IMA. J. Numer. Anal., 32, 227-245 (2012) · Zbl 1236.65043
[24] Jin, Z.-F.; Wang, Q.; Wan, Z., Recovering low-rank matrices from corrupted observations via the linear conjugate gradient algorithm, J. Comput. Appl. Math., 256, 114-120 (2014) · Zbl 1320.65068
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.