Penalty decomposition methods for rank minimization

References

• A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, Engineering Applications, MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, 2001.
   Google Scholar
• R. Bhatia, Matrix Analysis, Springer, New York, 1997.
   Google Scholar
• D. Brigo, A note on correlation and rank reduction (2002). Available at www.damianobrigo.it
   Google Scholar
• D. Brigo and F. Mercurio, Interest Rate Models: Theory and Practice, Springer, Berlin, 2001.
   Google Scholar
• S. Burer, R.D.C. Monteiro, and Y. Zhang, Maximum stable set formulations and heuristics based on continuous optimization, Math. Program. 94 (2002), pp. 137–166. doi: 10.1007/s10107-002-0356-4
   Web of Science ®Google Scholar
• J.-F. Cai, E.J. Candès, and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20(4) (2010), pp. 1956–1982.
   Google Scholar
• E.J. Candés and B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math. 9 (2009), pp. 717–772. doi: 10.1007/s10208-009-9045-5
   Web of Science ®Google Scholar
• W. Dai and O. Milenkovic, SET: An algorithm for consistent matrix completion, Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, Dallas, TX, 2010, pp. 3646–3649.
   Google Scholar
• L. Eldén, Matrix Methods in Data Mining and Pattern Recognition (Fundamentals of Algorithms), SIAM, Philadelphia, PA, 2009.
   Google Scholar
• M. Fazel, H. Hindi, and S.P. Boyd, A rank minimization heuristic with application to minimum order system approximation, Proc. Am. Control Conf. 6 (2001), pp. 4734–4739. doi: 10.1109/ACC.2001.945730
   Google Scholar
• M. Fornasier, H. Rauhut, and R. Ward, Low-rank matrix recovery via iteratively reweighted least squares minimization, SIAM J. Optim. 21 (2011), pp. 1614–1640. doi: 10.1137/100811404
   Web of Science ®Google Scholar
• T. Fushiki, Estimation of positive semidefinite correlation matrices by using convex quadratic semidefinite programming, Neural Comput. 21 (2009), pp. 2028–2048. doi: 10.1162/neco.2009.04-08-765
   PubMed Web of Science ®Google Scholar
• Y. Gao and D. Sun, A majorized penalty approach for calibrating rank constrained correlation matrix problems, Tech. Rep., Department of Mathematics, National University of Singapore, Singapore, 2010.
   Google Scholar
• M.X. Goemans and D.P. Williamson, .878-Approximation Algorithms for MAX CUT and MAX 2SAT, Proc. 26th STOC, ACM Press, New York, 1994, pp. 422–431.
   Google Scholar
• I. Grubiŝić and R. Pietersz, Efficient rank reduction of correlation matrices, Linear Algebra Appl. 422 (2007), pp. 629–653. doi: 10.1016/j.laa.2006.11.024
   Web of Science ®Google Scholar
• J.L. Herlocker, J.A. Konstan, A. Borchers, and J. Riedl, An Algorithmic Framework for Performing Collaborative Filtering, SIGIR Forum, New York, 1999, pp. 230–237.
   Google Scholar
• R.A. Horn and C.R. Johnson, Matrix Analysis, Cambridge University Press, New York, 1990.
   Google Scholar
• S. Ji, K.-F. Sze, Z. Zhou, A. So, and Y. Ye, Beyond Convex Relaxation: A Polynomial Time Nonconvex Optimization Approach to Network Localization, Proceedings of the 32nd IEEE International Conference on Computer Communications (INFOCOM 2013), 2013, pp. 2499–2507.
   Google Scholar
• R.H. Keshavan and S. Oh, A gradient descent algorithm on the Grassman manifold for matrix completion, Tech. Rep., Department of Electrical Engineering, Stanford University, Stanford, 2009.
   Google Scholar
• M. Lai, Y. Xu, and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed lq minimization, SIAM J. Numer. Anal. 5(2) (2013), pp. 927–957. doi: 10.1137/110840364
   Google Scholar
• K. Lee and Y. Bresler, Admira: Atomic decomposition for minimum rank approximation, IEEE Trans. Inform. Theory 56(9) (2010), pp. 4402–4416. doi: 10.1109/TIT.2010.2054251
   Web of Science ®Google Scholar
• A.S. Lewis, Derivatives of spectral functions, Math. Oper. Res. 21(3) (1996), pp. 576–588. doi: 10.1287/moor.21.3.576
   Web of Science ®Google Scholar
• Q. Li and H. Qi, A sequential semismooth Newton method for the nearest low-rank correlation matrix problem, SIAM J. Optim. 21 (2011), pp. 1641–1666. doi: 10.1137/090771181
   Web of Science ®Google Scholar
• Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM J. Matrix Anal. A 31 (2009), pp. 1235–1256. doi: 10.1137/090755436
   Web of Science ®Google Scholar
• Y. Liu, D. Sun, and K.C. Toh, An implementable proximal point algorithmic framework for nuclear norm minimization, Math. Program. 133 (2012), pp. 399–436. doi: 10.1007/s10107-010-0437-8
   Web of Science ®Google Scholar
• Z. Lu, R.D.C. Monteiro, and M. Yuan, Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression, Math. Program. 131 (2012), pp. 163–194. doi: 10.1007/s10107-010-0350-1
   Web of Science ®Google Scholar
• Z. Lu and Y. Zhang, Iterative reweighted singular value minimization methods for lp regularized unconstrained matrix minimization, Preprint (2014).
   Google Scholar
• S. Ma, D. Goldfarb, and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program. 128(1) (2011), pp. 321–353. doi: 10.1007/s10107-009-0306-5
   Web of Science ®Google Scholar
• R. Mazumder, T. Hastie, and R. Tibshirani, Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res. 11 (2010), pp. 2287–2232.
   PubMed Web of Science ®Google Scholar
• R. Meka, P. Jain, and I.S. Dhillon, Guaranteed Rank Minimization Via Singular Value Projection, NIPS, 2010, pp. 937–945. Available at http://papers.nips.cc/paper/3904-guaranteed-rank-minimization-via-singular-value-projection
   Google Scholar
• K. Mohan and M. Fazel, Iterative reweighted least squares for matrix rank minimization, 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton, IL, 2010, pp. 653–661.
   Google Scholar
• T. Mrita and T. Kanade, A sequential factorization method for recovering shape and motion from image streams, IEEE Trans. Pattern Anal. 19 (1997), pp. 858–867. doi: 10.1109/34.608289
   Web of Science ®Google Scholar
• R. Pietersz and I. Grubiŝić, Rank reduction of correlation matrices by majorization, Quant. Financ. 4 (2004), pp. 649–662. doi: 10.1080/14697680400016182
   Web of Science ®Google Scholar
• H. Qi and D. Sun, An augmented Lagrangian dual approach for the H-weighted nearest correlation matrix problem, IMA J. Numer. Anal. 31(2) (2011), pp. 491–511. doi: 10.1093/imanum/drp031
   Web of Science ®Google Scholar
• F. Rapisarda, D. Brigo, and F. Mercurio, Parameterizing correlations: A geometric interpretation, IMA J. Manage. Math. 18(1) (2007), pp. 55–73. doi: 10.1093/imaman/dpl010
   Google Scholar
• R. Rebonato, On the simultaneous calibration of multifactor lognormal interest rate models to Black volatilities and to the correlation matrix, J. Comput. Financ. 2 (1999), pp. 5–27.
   Google Scholar
• R. Rebonato, Modern Pricing and Interest-Rate Derivatives, Princeton University Press, Princeton, NJ, 2002.
   Google Scholar
• R. Rebonato, Interest-rate term-structure pricing models: A review, Proc. R. Soc. Lond. A 460 (2004), pp. 667–728. doi: 10.1098/rspa.2003.1255
   Web of Science ®Google Scholar
• B. Recht, M. Fazel, and P. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev. 52(3) (2010), pp. 471–501. doi: 10.1137/070697835
   Web of Science ®Google Scholar
• A. Ruszczyński, Nonlinear Optimization, Princeton University Press, Princeton, NJ, 2006.
   Google Scholar
• K. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pac. J. Optim. 6 (2010), pp. 615–640.
   Web of Science ®Google Scholar
• C. Tpmasi and T. Kanade, Shape and motion from image streams under orthography: A factorization method, Int. J. Comput. Vis. 9 (1992), pp. 137–154. doi: 10.1007/BF00129684
   Web of Science ®Google Scholar
• P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001), pp. 475–494. doi: 10.1023/A:1017501703105
   Web of Science ®Google Scholar
• E. van den Berg and M.P. Friedlander, Sparse optimization with least-squares constraints, SIAM J. Optim. 21(4) (2011), pp. 1201–1229. doi: 10.1137/100785028
   Web of Science ®Google Scholar
• Z. Wen, W. Yin, and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput. 4 (2012), pp. 333–361. doi: 10.1007/s12532-012-0044-1
   Google Scholar
• L. Wu, Fast at-the-money calibration of the LIBOR market model using Lagrangian multipliers, J. Comput. Financ. 6 (2003), pp. 39–77.
   Google Scholar
• Z. Zhang and L. Wu, Optimal low-rank approximation to a correlation matrix, Linear Algebra Appl. 364 (2003), pp. 161–187. doi: 10.1016/S0024-3795(02)00551-7
   Web of Science ®Google Scholar