TY - GEN
T1 - Guaranteed Matrix Completion via Nonconvex Factorization
AU - Sun, Ruoyu
AU - Luo, Zhi Quan
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2015/12/11
Y1 - 2015/12/11
N2 - Matrix factorization is a popular approach for large-scale matrix completion. In this approach, the unknown low-rank matrix is expressed as the product of two much smaller matrices so that the low-rank property is automatically fulfilled. The resulting optimization problem, even with huge size, can be solved (to stationary points) very efficiently through standard optimization algorithms such as alternating minimization and stochastic gradient descent (SGD). However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of the factorization based formulation, and recover the true low-rank matrix. A major difference of our work from the existing results is that we do not need resampling (i.e., Using independent samples at each iteration) in either the algorithm or its analysis. To the best of our knowledge, our result is the first one that provides exact recovery guarantee for many standard algorithms such as gradient descent, SGD and block coordinate gradient descent.
AB - Matrix factorization is a popular approach for large-scale matrix completion. In this approach, the unknown low-rank matrix is expressed as the product of two much smaller matrices so that the low-rank property is automatically fulfilled. The resulting optimization problem, even with huge size, can be solved (to stationary points) very efficiently through standard optimization algorithms such as alternating minimization and stochastic gradient descent (SGD). However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of the factorization based formulation, and recover the true low-rank matrix. A major difference of our work from the existing results is that we do not need resampling (i.e., Using independent samples at each iteration) in either the algorithm or its analysis. To the best of our knowledge, our result is the first one that provides exact recovery guarantee for many standard algorithms such as gradient descent, SGD and block coordinate gradient descent.
KW - matrix completion
KW - matrix factorization
KW - nonconvex optimization
KW - perturbation analysis
UR - http://www.scopus.com/inward/record.url?scp=84960383894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960383894&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2015.25
DO - 10.1109/FOCS.2015.25
M3 - Conference contribution
AN - SCOPUS:84960383894
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 270
EP - 289
BT - Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015
PB - IEEE Computer Society
T2 - 56th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2015
Y2 - 17 October 2015 through 20 October 2015
ER -