Low-Rank Matrix Learning Using Biconvex Surrogate Minimization - Hu, E. (IEEE Xplore, 2020)
Many machine learning problems involve learning a low-rank positive semideﬁnite matrix. However, existing solvers for this low-rank semideﬁnite program (SDP) are often expensive. In this paper, by factorizing the target matrix as a product of two matrices and using a Courant penalty to penalize for their difference, we reformulate the SDP as a biconvex optimization problem. This allows the use of multiconvex optimization techniques to deﬁne simple surrogates, which can be minimized easily by block coordinate descent. Moreover, while traditionally this biconvex problem approaches the original problem only when the penalty parameter is inﬁnite, we show that the two problems are equivalent when the penalty parameter is sufﬁciently large. Experiments on a number of SDP applications in machine learning show that the proposed algorithm is as accurate as other state-of-the-art algorithms, but is much faster, especially on large data sets.