SNIG PROPERTY OF MATRIX LOW-RANK FACTORIZATION MODEL

doi:10.4208/jcm.1707-m2016-0796

Journal of Computational Mathematics ›› 2018, Vol. 36 ›› Issue (3): 374-390.DOI: 10.4208/jcm.1707-m2016-0796

Previous Articles Next Articles

SNIG PROPERTY OF MATRIX LOW-RANK FACTORIZATION MODEL

Hong Wang¹, Xin Liu², Xiaojun Chen¹, Yaxiang Yuan²

1. Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China;
2. State Key Laboratory of Scientific and Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China

Received:2016-11-22 Revised:2017-05-02 Online:2018-05-15 Published:2018-05-15
Supported by:
The work of Xin Liu is supported in part by NSFC grants 11471325, 11331012 and 11461161005, China 863 Program 2013AA122902 and the National Center for Mathematics and Interdisciplinary Sciences, CAS. The work of Xiaojun Chen is supported in part by NSFC/Hong Kong Research Grant Council N-PolyU504/14. The work of Ya-xiang Yuan is supported in part by NSFC grants 11331012 and 11461161005.

PDF ( 123 ) Cited

Hong Wang, Xin Liu, Xiaojun Chen, Yaxiang Yuan. SNIG PROPERTY OF MATRIX LOW-RANK FACTORIZATION MODEL[J]. Journal of Computational Mathematics, 2018, 36(3): 374-390.

zRecently, the matrix factorization model attracts increasing attentions in handling large-scale rank minimization problems, which is essentially a nonconvex minimization problem. Specifically, it is a quadratic least squares problem and consequently a quartic polynomial optimization problem. In this paper, we introduce a concept of the SNIG ("Second-order Necessary optimality Implies Global optimality") condition which stands for the property that any second-order stationary point of the matrix factorization model must be a global minimizer. Some scenarios under which the SNIG condition holds are presented. Furthermore, we illustrate by an example when the SNIG condition may fail.

Key words: Low rank factorization, Nonconvex optimization, Second-order optimality condition, Global minimizer

CLC Number:

[1] Y. Koren, R. Bell, C. Volinsky, Matrix factorization techniques for recommender systems. IEEE, (2009), 30-37.

[2] S. Burer, R.D.C Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. Ser. B, 95(2013), 329-357.

[3] J. Cai, E. Candès, Z. Shen, A singular value thresholding algorithm for matrix completion. SIAM J. Optim., 20(2010), 1956-1982.

[4] E. Candès, B. Recht, Exact matrix completion via convex optimization. Found. Comput. Math., 9(2008), 717-772.

[5] E. Candès, T. Tao, The power of convex relaxation:near-optimal matrix completion. IEEE Trans. Inform. Theory, 56(2009), 2053-2080.

[6] V. Chandrasekaran, S. Sanghavi, P.A. Parrilo, A.S. Willsky, Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim., 21(2011), 572-596.

[7] C. Chen, B. He, X. Yuan, Matrix completion via alternating direction methods. IMA J. Numer. Anal., 32(2012), 227-245.

[8] G. Takács, I. Pilászy, B. Németh, D. Tikk, Major components of the gravity recommendation system. ACM SIGKDD Explorations Newsletter, 9(2007), 80-83.

[9] E. Candès, X. Li, M. Soltanolkotabi, Phase retrieval via Wirtinger flow:Theory and algorithms. IEEE Trans. on Inform. Theory, 61(2015), 1985-2007.

[10] G. Rong, Jason D. Lee and T. Ma, Matrix Completion has No Spurious Local Minimum. arXiv:1605.07272

[11] D. Goldfarb, S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization. Found. Comput. Math., 11(2011), 183-210.

[12] M. Hardt, Understanding alternating minimization for matrix completion. arXiv:1312.0925.

[13] P. Jain, P. Netrapalli, S. Sanghavi, Low-rank matrix completion using alternating minimization. in Proc. 45th Symposium on Theory of Computing, 2013, pp. 665-674.

[14] M. Journe, F. Bach, P.-A. Absil, R. Sepulchre, Low-rank optimization on the cone of positive semidefinite matrices. SIAM J. Optim., 20(2010), 2327-2351.

[15] X. Liu, Z. Wen, Y. Zhang, Limited memory block Krylov subspace optimization for computing dominant singular value decompositions. SIAM J. Sci. Comput., 35(2013), A1641-A1668.

[16] X. Liu, Z. Wen, Y. Zhang, An efficient Gauss-Newton algorithm for symmetric low-rank product matrix approximations. SIAM J. Optim, 25(2015), 1571?608.

[17] Z. Lu, Y. Zhang, Penalty decomposition methods for rank minimization. under review.

[18] S. Ma, D. Goldfarb, L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. Ser. A, 128(2011), 321-353.

[19] B. Mishra, G. Meyer, F. Bach, R. Sepulchre, Low-rank optimization with trace norm penalty. SIAM J. Optim., 23(2013), 2124-2149.

[20] K. Murty, S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming. Math. Program., 39(1987), 117-129.

[21] Singh, P. Ajit, Gordon, J. Geoffrey, A unified view of matrix factorization models. Springer, 358-373(2008).

[22] R. Sun, Z. Luo, Guaranteed matrix completion via non-convex factorization.arXiv:1411.8003.

[23] B. Recht, M. Fazel, A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review, 52(2010), 471-501.

[24] S. Oymak, K. Mohan, M. Fazel, B. Hassibi, A simplified approach to recovery conditions for low rank matrices. IEEE International Symposium on Information Theory(2011).

[25] S. Oymak, B. Hassibi, New null space results and recovery thresholds for matrix rank minimization. IEEE International Symposium on Information Theory(2011).

[26] Z. Wang, M. Lai, Z. Lu, J. Ye, Orthogonal rank-one matrix pursuit for matrix completion. under review.

[27] Z. Wen, C. Yang, X. Liu, Y. Zhang, Trace-penalty minimization for large-scale eigenspace computation. under review at J. Sci. Comput..

[28] Z. Wen, W. Yin, Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4(2012), 333-361.

[29] Z. Zhu, A. So, Y. Ye, Fast and near-optimal matrix completion via randomized basis pursuit. Proceed. of the Fifth International Congress of Chinese Mathematicians, ser. AMS/IP Studi. Adv. Math., 51(2009), 859-882.

[1]	Yanping Wang, Chuanlong Wang . The Second-Order Optimality Conditions for Variable Programming [J]. Journal of Computational Mathematics, 2008, 26(5): 756-766.
[2]	Wen Yu SUN,Raimundo.J.B. Sampaio,M.A.B. Candido. PROXIMAL POINT ALGORITHM FOR MINIMIZATION OF DC FUNCTION [J]. Journal of Computational Mathematics, 2003, 21(4): 451-462.
[3]	Xiong Da CHEN,Ya Xiang YUAN. ON MAXIMA OF DUAL FUNCTION OF THE CDT SUBPROBLEM [J]. Journal of Computational Mathematics, 2001, 19(2): 113-124.

Viewed

Full text

Abstract

SNIG PROPERTY OF MATRIX LOW-RANK FACTORIZATION MODEL

扫码分享