Journal
SIAM JOURNAL ON IMAGING SCIENCES
Volume 11, Issue 4, Pages 2165-2204Publisher
SIAM PUBLICATIONS
DOI: 10.1137/17M1150189
Keywords
nonconvex optimization; matrix factorization; low-rank minimization
Ask authors/readers for more resources
A rank-r matrix X is an element of R-mxn can be written as a product UVT, where U is an element of R(mxr )and V is an element of R-nxr. One could exploit this observation in optimization: e.g., consider the minimization of a convex function f(X) over rank-r matrices, where the set of low-rank matrices is modeled via UVT . Though such parameterization reduces the number of variables and is more computationally efficient (of particular interest is the case r << min{m, n}), it comes at a cost: f(UVT) becomes a nonconvex function w.r.t. U and V. We study such parameterization on generic convex objectives f and focus on firstorder, gradient descent algorithms. We propose the bifactored gradient descent (BFGD) algorithm, an efficient first-order method that operates directly on the U, V factors. We show that when f is (restricted) smooth, BFGD has local sublinear convergence; when f is both (restricted) smooth and (restricted) strongly convex, it has local linear convergence. For several applications, we provide simple and efficient initialization schemes that provide initial conditions, good enough for the above convergence results to hold, globally. Extensive experimental results support our arguments that BFGD is an efficient and accurate nonconvex method, compared to state-of-the-art approaches.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available