nips nips2011 nips2011-211 nips2011-211-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yong Zhang, Zhaosong Lu
Abstract: In this paper we consider general rank minimization problems with rank appearing in either objective function or constraint. We first show that a class of matrix optimization problems can be solved as lower dimensional vector optimization problems. As a consequence, we establish that a class of rank minimization problems have closed form solutions. Using this result, we then propose penalty decomposition methods for general rank minimization problems. The convergence results of the PD methods have been shown in the longer version of the paper [19]. Finally, we test the performance of our methods by applying them to matrix completion and nearest low-rank correlation matrix problems. The computational results demonstrate that our methods generally outperform the existing methods in terms of solution quality and/or speed. 1
[1] A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization: Analysis, algorithms, Engineering Applications. MPS-SIAM Series on Optimization, SIAM, Philadelphia, PA, USA, 2001.
[2] M. Bertalm´o, G. Sapiro, V. Caselles and V. Ballester. Image inpainting. SIGGRAPH 2000, ı New Orleans, USA, 2000.
[3] D. Brigo. A note on correlation and rank reduction. Available at www.damianobrigo.it, 2002.
[4] D. Brigo and F. Mercurio. Interest Rate Models: Theory and Practice. Springer-Verlag, Berlin, 2001.
[5] S. Burer, R. D. C. Monteiro, and Y. Zhang. Maximum stable set formulations and heuristics based on continuous optimization. Math. Program., 94:137-166, 2002.
[6] J.-F. Cai, E. J. Cand` s, and Z. Shen. A singular value thresholding algorithm for matrix come pletion. Technical report, 2008.
[7] E. J. Cand´ s and B. Recht. Exact matrix completion via convex optimization. Found. Comput. e Math., 2009.
[8] W. Dai and O. Milenkovic. SET: an algorithm for consistent matrix completion. Technical report, Department of Electrical and Computer Engineering, University of Illinois, 2009.
[9] L. Eld´ n. Matrix methods in data mining and pattern recognition (fundamentals of algorithms). e SIAM, Philadelphia, PA, USA, 2009.
[10] M. Fazel, H. Hindi, and S. P. Boyd. A rank minimization heuristic with application to minimum order system approximation. P. Amer. Contr. Conf., 6:4734-4739, 2001.
[11] M. X. Goemans and D. P. Williamson. .878-approximation algorithms for MAX CUT and MAX 2SAT. Lect. Notes Comput. Sc., 422-431, 1994.
[12] I. Grubiˆi´ and R. Pietersz. Efficient rank reduction of correlation matrices. Linear Algebra sc Appl., 422:629-653, 2007.
[13] R. H. Keshavan and S. Oh. A gradient descent algorithm on the Grassman manifold for matrix completion. Technical report, Department of Electrical Engineering, Stanford University, 2009.
[14] K. Lee and Y. Bresler. Admira: Atomic decomposition for minimum rank approximation. Technical report, University of Illinois, Urbana-Champaign, 2009. 8
[15] Q. Li and H. Qi. A sequential semismooth Newton method for the nearest low-rank correlation matrix problem. Technical report, School of Mathematics, University of Southampton, UK, 2009.
[16] Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. A., 31:1235-1256, 2009.
[17] Y. Liu, D. Sun, and K. C. Toh. An implementable proximal point algorithmic framework for nuclear norm minimization. Technical report, National University of Singapore, 2009.
[18] Z. Lu, R. D. C. Monteiro, and M. Yuan. Convex optimization methods for dimension reduction and coefficient estimation in Multivariate Linear Regression. Accepted in Math. Program., 2008.
[19] Z. Lu and Y. Zhang. Penalty decomposition methods for rank minimization. Technical report, Department of Mathematics, Simon Fraser University, Canada, 2010.
[20] Z. Lu and Y. Zhang. Penalty decomposition methods for l0 minimization. Technical report, Department of Mathematics, Simon Fraser University, Canada, 2010.
[21] R. Mazumder, T. Hastie, and R. Tibshirani. Regularization methods for learning incomplete matrices. Technical report, Stanford University, 2009.
[22] S. Ma, D. Goldfarb, and L. Chen. Fixed point and Bregman iterative methods for matrix rank minimization. To appear in Math. Program., 2008.
[23] R. Meka, P. Jain and I. S. Dhillon. Guaranteed rank minimization via singular value projection. Technical report, University of Texas at Austin, 2009.
[24] T. Mrita and T. Kanade. A sequential factorization method for recovering shape and motion from image streams. IEEE T. Pattern Anal., 19:858-867, 1997.
[25] R. Pietersz and I. Grubiˆi´ . Rank reduction of correlation matrices by majorization. Quant. sc Financ., 4:649-662, 2004.
[26] F. Rapisarda, D. Brigo and F. Mercurio. Parametrizing correlations: a geometric interpretation. Banca IMI Working Paper, 2002 (www.fabiomercurio.it).
[27] B. Recht, M. Fazel, and P. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. To appear in SIAM Rev., 2007.
[28] R. Rebonato. On the simultaneous calibration of multifactor lognormal interest rate models to Black volatilities and to the correlation matrix. J. Comput. Financ., 2:5-27, 1999.
[29] R. Rebonato. Modern Pricing and Interest-Rate Derivatives. Princeton University Press, New Jersey, 2002.
[30] R. Rebonato. Interest-rate term-structure pricing models: a review. P. R. Soc. Lond. A-Conta., 460:667-728, 2004.
[31] J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the International Conference of Machine Learning, 2005.
[32] K. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Accepted in Pac. J. Optim., 2009.
[33] C. Tpmasi and T. Kanade. Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vision, 9:137-154, 1992.
[34] E. van den Berg and M. P. Friedlander. Sparse optimization with least-squares constraints. Technical Report, University of British Columbia, Vancouver, 2010.
[35] Z. Wen, W. Yin, and Y. Zhang. Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Technical report, Department of Computational and Applied Mathematics, Rice University, 2010.
[36] L. Wu. Fast at-the-money calibration of the LIBOR market model using Lagrangian multipliers. J. Comput. Financ., 6:39-77, 2003.
[37] J. Yang and X. Yuan. An inexact alternating direction method for trace norm regularized least squares problem. Technical report, Department of Mathematics, Nanjing University, China, 2010.
[38] Z. Zhang and L. Wu. Optimal low-rank approximation to a correlation matrix. Linear Algebra Appl., 364:161-187, 2003. 9