Finding low-rank solutions to smooth convex problems via the Burer-Monteiro approach

摘要: A rank-r matrix X ∈ ℝm×n can be written as a product UV ⊤, where U ℝm×r and V ℝn×r. One could exploit this observation in optimization: e.g., consider the minimization of convex function ƒ(X) over matrices, set matrices is modeled via factorization variables. Such heuristic has been widely used before for problem instances, solution (approximately) low-rank. Though such parameterization reduces number variables more efficient w.r.t. computational memory requirements (of particular interest case r ≪ min{m, n}), it comes at cost: ƒ(UV ⊤) becomes non-convex V. In paper, we study optimizing generic smooth ƒ, that Lipschitz continuous gradients, focus on first-order, gradient descent algorithmic solutions. We propose Bi-Factored Gradient Descent (BFGD) algorithm, an first-order method operates U, factors. show when ƒ BFGD initialized properly, local sublinear convergence to globally optimum point. As test case, 1-bit completion problem: compare with state-of-the-art approaches least competitive error performance real dataset experiments, while being faster execution, compared rest algorithms. conclude work some remarks open questions further investigations.