Convergence of fixed-point continuation algorithms for matrix rank minimization. (English) Zbl 1219.90195

Summary: The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, S. Ma, D. Goldfarb and L. Chen [Math. Program. 128, No. 1–2 (A), 321–353 (2011; Zbl 1221.65146)] proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem. By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.


90C59 Approximation methods and heuristics in mathematical programming
15B52 Random matrices (algebraic aspects)
15A18 Eigenvalues, singular values, and eigenvectors


Zbl 1221.65146
Full Text: DOI arXiv


[1] T. Blumensath, M.E. Davies, Gradient pursuits, IEEE Trans. Signal Process. 56(6), 2370–2382 (2008). · Zbl 1390.94102
[2] T. Blumensath, M.E. Davies, Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal. 27(3), 265–274 (2009). · Zbl 1174.94008
[3] J.M. Borwein, A.S. Lewis, Convex Analysis and Nonlinear Optimization (Springer, Berlin, 2003).
[4] J. Cai, E.J. Candès, Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20(4), 1956–1982 (2010). · Zbl 1201.90155
[5] E.J. Candès, Y. Plan, Matrix completion with noise, Proc. IEEE (2009).
[6] E.J. Candès, B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math. 9, 717–772 (2009). · Zbl 1219.90124
[7] E.J. Candès, J. Romberg, 1-MAGIC: Recovery of sparse signals via convex programming, Tech. rep., Caltech, 2005.
[8] E.J. Candès, T. Tao, The power of convex relaxation: near-optimal matrix completion, IEEE Trans. Inf. Theory 56(5), 2053–2080 (2009). · Zbl 1366.15021
[9] E.J. Candès, J. Romberg, T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory 52, 489–509 (2006). · Zbl 1231.94017
[10] Rice compressed sensing website. http://dsp.rice.edu/cs .
[11] W. Dai, O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inf. Theory 55(5), 2230–2249 (2009). · Zbl 1367.94082
[12] D. Donoho, Compressed sensing, IEEE Trans. Inf. Theory 52, 1289–1306 (2006). · Zbl 1288.94016
[13] D.L. Donoho, Y. Tsaig, Fast solution of 1-norm minimization problems when the solution may be sparse, IEEE Trans. Inf. Theory 54(11), 4789–4812 (2008). · Zbl 1247.94009
[14] D. Donoho, Y. Tsaig, I. Drori, J.-C. Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit, Tech. rep., Stanford University, 2006. · Zbl 1365.94069
[15] P. Drineas, R. Kannan, M.W. Mahoney, Fast Monte Carlo algorithms for matrices II: Computing low-rank approximations to a matrix, SIAM J. Comput. 36, 158–183 (2006). · Zbl 1111.68148
[16] M. Fazel, H. Hindi, S. Boyd, A rank minimization heuristic with application to minimum order system approximation, in Proceedings of the American Control Conference, vol. 6 (2001), pp. 4734–4739.
[17] M. Fazel, H. Hindi, S. Boyd, Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices, in Proceedings of the American Control Conference (2003), pp. 2156–2162.
[18] M. Fazel, H. Hindi, S. Boyd, Rank minimization and applications in system theory, in American Control Conference (2004), pp. 3273–3278.
[19] M.A.T. Figueiredo, R.D. Nowak, S.J. Wright, Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J. Sel. Top. Signal Process. 1, 4 (2007).
[20] L.E. Ghaoui, P. Gahinet, Rank minimization under LMI constraints: A framework for output feedback problems, in Proceedings of the European Control Conference (1993).
[21] E.T. Hale, W. Yin, Y. Zhang, Fixed-point continuation for 1-minimization: Methodology and convergence, SIAM J. Optim. 19(3), 1107–1130 (2008). · Zbl 1180.65076
[22] J.-B. Hiriart-Urruty, C. Lemaréchal, Convex Analysis and Minimization Algorithms II: Advanced Theory and Bundle Methods (Springer, New York, 1993).
[23] R.H. Keshavan, A. Montanari, S. Oh, Matrix completion from noisy entries (2009). arXiv:0906.2027 . · Zbl 1242.62069
[24] R.H. Keshavan, A. Montanari, S. Oh, Matrix completion from a few entries, IEEE Trans. Inf. Theory 56, 2980–2998 (2010). · Zbl 1242.62069
[25] S.J. Kim, K. Koh, M. Lustig, S. Boyd, D. Gorinevsky, A method for large-scale 1-regularized least-squares, IEEE J. Sel. Top. Signal Process. 4(1), 606–617 (2007).
[26] R.M. Larsen, PROPACK–software for large and sparse SVD calculations, available from http://sun.stanford.edu/\(\sim\)rmunk/PROPACK .
[27] K. Lee, Y. Bresler, ADMIRA: atomic decomposition for minimum rank approximation (2009). arXiv:0905.0044 . · Zbl 1366.94112
[28] K. Lee, Y. Bresler, Efficient and guaranteed rank minimization by atomic decomposition (2009). arXiv:0901.1898v1 .
[29] K. Lee, Y. Bresler, Guaranteed minimum rank approximation from linear observations by nuclear norm minimization with an ellipsoidal constraint (2009). arXiv:0903.4742 .
[30] N. Linial, E. London, Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15, 215–245 (1995). · Zbl 0827.05021
[31] Y. Liu, D. Sun, K.-C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Preprint, National University of Singapore, 2009. · Zbl 1262.90125
[32] Z. Liu, L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. Appl. 31(3), 1235–1256 (2009). · Zbl 1201.90151
[33] S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program. (2009). doi: 10.1007/s10107-009-0306-5 . · Zbl 1221.65146
[34] R. Meka, P. Jain, I.S. Dhillon, Guaranteed rank minimization via singular value projection (2009). arXiv:0909.5457 .
[35] B.K. Natarajan, Sparse approximate solutions to linear systems, SIAM J. Comput. 24, 227–234 (1995). · Zbl 0827.68054
[36] D. Needell, J.A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal. 26, 301–321 (2009). · Zbl 1163.94003
[37] Netfix prize website. http://www.netflixprize.com/ .
[38] B. Recht, M. Fazel, P. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev. 52(3), 471–501 (2010). · Zbl 1198.90321
[39] E. Sontag, Mathematical Control Theory (Springer, New York, 1998). · Zbl 0945.93001
[40] N. Srebro, Learning with Matrix Factorizations. PhD thesis, Massachusetts Institute of Technology, 2004.
[41] N. Srebro, T. Jaakkola, Weighted low-rank approximations, in Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003) (2003).
[42] R. Tibshirani, Regression shrinkage and selection via the lasso, J. R. Stat. Soc. B 58, 267–288 (1996). · Zbl 0850.62538
[43] K.-C. Toh, S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim. 6, 615–640 (2010). · Zbl 1205.90218
[44] K.-C. Toh, M.J. Todd, R.H. Tütüncü, SDPT3–a Matlab software package for semidefinite programming, Optim. Methods Softw. 11, 545–581 (1999). · Zbl 0997.90060
[45] J. Tropp, Just relax: Convex programming methods for identifying sparse signals, IEEE Trans. Inf. Theory 51, 1030–1051 (2006). · Zbl 1288.94025
[46] E. van den Berg, M.P. Friedlander, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput. 31(2), 890–912 (2008). · Zbl 1193.49033
[47] W. Yin, S. Osher, D. Goldfarb, J. Darbon, Bregman iterative algorithms for 1-minimization with applications to compressed sensing, SIAM J. Imaging Sci. 1(1), 143–168 (2008). · Zbl 1203.90153
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.