jmlr jmlr2012 jmlr2012-52 jmlr2012-52-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Karthik Mohan, Maryam Fazel
Abstract: The problem of minimizing the rank of a matrix subject to affine constraints has applications in several areas including machine learning, and is known to be NP-hard. A tractable relaxation for this problem is nuclear norm (or trace norm) minimization, which is guaranteed to find the minimum rank matrix under suitable assumptions. In this paper, we propose a family of Iterative Reweighted Least Squares algorithms IRLS-p (with 0 ≤ p ≤ 1), as a computationally efficient way to improve over the performance of nuclear norm minimization. The algorithms can be viewed as (locally) minimizing certain smooth approximations to the rank function. When p = 1, we give theoretical guarantees similar to those for nuclear norm minimization, that is, recovery of low-rank matrices under certain assumptions on the operator defining the constraints. For p < 1, IRLSp shows better empirical performance in terms of recovering low-rank matrices than nuclear norm minimization. We provide an efficient implementation for IRLS-p, and also present a related family of algorithms, sIRLS-p. These algorithms exhibit competitive run times and improved recovery when compared to existing algorithms for random instances of the matrix completion problem, as well as on the MovieLens movie recommendation data set. Keywords: matrix rank minimization, matrix completion, iterative algorithms, null-space property
B.J. Dahlen, J.A. Konstan, J. Herlocker, N. Good, A. Borchers, and J. Riedl. “Movie lens data”. 1998. http://www.grouplens.org/node/73. A. Argyriou. A study of convex regularizers for sparse recovery and feature selection. 2010. Technical Report. Available at http://ttic.uchicago.edu/˜argyriou/papers/sparse_report. pdf. A. Argyriou, C.A. Micchelli, M. Pontil, and Y. Ying. A spectral regularization framework for multitask structure learning. In Proc. of Neural Information Processing Systems (NIPS), 2007. J.F. Cai, E.J. Candes, and Z. Shen. A singular value thresholding algorithm for matrix completion. SIAM J. on Optimization, 20(4):1956–1982, 2008. E. J. Candes and S. Becker. Software for singular value thresholding algorithm for matrix completion. 2010. Available at http://svt.caltech.edu/code.html. E. J. Candes and B. Recht. Exact matrix completion via convex optimziation. Foundations of Computational Mathematics, 9:717–772, 2009. E. J. Candes and T. Tao. Decoding by linear programming. IEEE Trans Info. Theory, 2004. E. J. Candes, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58(3), 2011. E.J. Candes, M.B. Wakin, and S. Boyd. Enhancing sparsity by reweighted l1 minimization. Journal of Fourier Analysis and Applications, 14:877–905, 2008. 3470 I TERATIVE R EWEIGHTED A LGORITHMS FOR M ATRIX R ANK M INIMIZATION V. Chandrasekaran, P.A. Parrilo, and A.S. Willsky. Latent variable graphical model selection via convex optimization. Annals of Statistics, forthcoming. V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky. The convex geometry of linear inverse problems. Journal of the Foundations of Compuataional Mathematics, forthcoming. V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix decomposition. SIAM Journal on Optimization, 21(2):572–596, 2011. R. Chartrand and V. Staneva. Restricted isometry properties and nonconvex compressive sensing. Inverse Problems, 24(035020):1–14, 2008. R. Chartrand and W. Yin. Iteratively reweighted algorithms for compressive sensing. In 33rd International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2008. I. Daubechies, R. DeVore, M. Fornasier, and C.S. Gunturk. Iteratively re-weighted least squares minimization for sparse recovery. Commun. Pure Appl. Math, 63(1):1–38, 2010. P. Drineas, R. Kannan, and M. W. Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low rank approximation to a matrix. SIAM Journal on Computing, 36:158–183, 2006. M. Fazel, H. Hindi, and S. Boyd. A rank minimization heuristic with application to minimum order system approximation. In Proc. American Control Conference, Arlington, VA, 2001. M. Fazel, H. Hindi, and S. Boyd. Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. In Proc. American Control Conference, pages 2156– 2162, Denver, CO, 2003. M. Fornasier, H. Rauhut, and R. Ward. Low-rank matrix recovery via iteratively reweighted least squares minimization. SIAM Journal of Optimization, 21(4), 2011. M. Fornasier, H. Rauhut and R. Ward. Code for IRLSM. Available at http://www.ma.utexas. edu/users/rward/. R. Garg and R. Khandekar. Gradient descent with sparsification: An iterative algorithm for sparse recovery with restricted isometry property. In Proc. of 26th Intl. Conf. on Machine Learning (ICML), 2009. D. Goldfarb and S. Ma. Convergence of fixed point continuation algorithms for matrix rank minimization. Foundations of Computational Mathematics, 11(2), 2011. D. Goldfarb and S. Ma. FPCA code. 2009. Available at http://www.columbia.edu/˜sm2756/ FPCA.htm. D. Gross, Y. K. Liu, S. T. Flammia, S. Becker, and J. Eisert. Quantum state tomography via compressed sensing. Physical Review Letters, 105, 2010. 3471 M OHAN AND FAZEL N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217–288, 2011. R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1990. R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991. R. H. Keshavan and S. Oh. A gradient descent algorithm on the grassman manifold for matrix completion. 2009. Available at http://arxiv.org/abs/0910.5260. R. H. Keshavan, A. Montanari, and S. Oh. Optspace algorithm. 2009a. http://www.stanford. edu/˜raghuram/optspace/index.html. R. H. Keshavan, A. Montanari, and S. Oh. Low-rank matrix completion with noisy observations: a quantitative comparison. In Proc. 47th Annual Allerton Conference on Communication, Control, and Computing, 2009b. K. Lee and Y. Bresler. Admira: Atomic decomposition for minimum rank approximation. IEEE Tran. Info. Theory, 56(9), 2010. A.S. Lewis. Derivatives of spectral functions. Mathematics of Operations Research, 21(3):576–588, 1996. Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Analysis and Appl., 31(3), 2008. M. S. Lobo, M. Fazel, and S. Boyd. Portfolio optimization with linear and fixed transaction costs. Annals of Operations Research, 152:341–365, 2006. A. W. Marshall and I. Olkin. Inequalities: Theory of Majorization and Its Applications. 1979. R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11:2287 – 2322, 2010. R. Meka, P. Jain, and I. S. Dhillon. Guaranteed rank minimization via singular value projection. In Proc. of Neural Information Processing Systems (NIPS), 2010. K. Mohan and M. Fazel. Reweighted nuclear norm minimization with application to system identification. In Proc. American Control Conference, Baltimore, MA, 2010a. K. Mohan and M. Fazel. Iterative reweighted least squares for matrix rank minimization. In Proc. 48th Allerton Conference on Controls and Communications, Allerton, IL, 2010b. D. Needell. Noisy signal recovery via iterative reweighted l1-minimization. In Proc. Asilomar Conference on Signals, Systems and Computers, 2009. 3472 I TERATIVE R EWEIGHTED A LGORITHMS FOR M ATRIX R ANK M INIMIZATION D. Needell and J. A. Tropp. Cosamp: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis, 26(3):301–321, 2008. S. Oymak and B. Hassibi. New null space results and recovery thresholds for matrix rank minimization. 2010. Available at http://arxiv.org/abs/1011.6326. S. Oymak, K. Mohan, M. Fazel, and B. Hassibi. A simplified approach to recovery conditions for low rank matrices. In Proc. International Symposium on Information Theory, 2011. B. D. Rao and K. Kreutz-Delgado. An affine scaling methodology for best basis selection. IEEE Transactions on Signal Processing, 47:187–200, 1999. N. Srebro, J.D.M. Rennie, and T.S. Jakkola. Maximum-margin matrix factorization. In Advances in Neural Information Processing Systems, 2005b. W. Tan, G. Cheung, and Y. Ma. Face recovery in conference video streaming using robust principal component analysis. In Proc. IEEE Intl. Conf. on Image Processing, 2011. K. C. Toh and S. W. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problem. Pacific Journal of Optimization, 6:615–640, 2010. D. P. Wipf and S. Nagarajan. Iterative reweighted ℓ1 and ℓ2 methods for finding sparse solutions. Journal of Selected Topics in Signal Proessing (Special Issue on Compressive Sensing), 4(2), 2010. T. Zhang. Analysis of multi-stage convex relaxation for sparse regularization. Journal of Machine Learning Research, 11:1081–1107, 2010. 3473