TY - JOUR
T1 - A nonconvex optimization framework for low rank matrix estimation
AU - Zhao, Tuo
AU - Wang, Zhaoran
AU - Liu, Han
N1 - Funding Information:
Research supported by NSF IIS1116730, NSF IIS1332109, NSF IIS1408910, NSF IIS1546482-BIGDATA, NSF DMS1454377-CAREER, NIH R01GM083084, NIH R01HG06841, NIH R01MH102339, and FDA HHSF223201000072C.
PY - 2015
Y1 - 2015
N2 - We study the estimation of low rank matrices via nonconvex optimization. Compared with convex relaxation, nonconvex optimization exhibits superior empirical performance for large scale instances of low rank matrix estimation. However, the understanding of its theoretical guarantees are limited. In this paper, we define the notion of projected oracle divergence based on which we establish sufficient conditions for the success of nonconvex optimization. We illustrate the consequences of this general framework for matrix sensing. In particular, we prove that a broad class of nonconvex optimization algorithms, including alternating minimization and gradient-type methods, geometrically converge to the global optimum and exactly recover the true low rank matrices under standard conditions.
AB - We study the estimation of low rank matrices via nonconvex optimization. Compared with convex relaxation, nonconvex optimization exhibits superior empirical performance for large scale instances of low rank matrix estimation. However, the understanding of its theoretical guarantees are limited. In this paper, we define the notion of projected oracle divergence based on which we establish sufficient conditions for the success of nonconvex optimization. We illustrate the consequences of this general framework for matrix sensing. In particular, we prove that a broad class of nonconvex optimization algorithms, including alternating minimization and gradient-type methods, geometrically converge to the global optimum and exactly recover the true low rank matrices under standard conditions.
UR - http://www.scopus.com/inward/record.url?scp=84965183190&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84965183190&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:84965183190
SN - 1049-5258
VL - 2015-January
SP - 559
EP - 567
JO - Advances in Neural Information Processing Systems
JF - Advances in Neural Information Processing Systems
T2 - 29th Annual Conference on Neural Information Processing Systems, NIPS 2015
Y2 - 7 December 2015 through 12 December 2015
ER -