A Majorization-Minimization Gauss-Newton Method for 1-Bit Matrix Completion
This addresses matrix completion from binary observations, a common problem in recommendation systems and surveys, but it is incremental as it builds on existing optimization principles.
The paper tackles 1-bit matrix completion by proposing the MMGN method, which uses majorization-minimization and Gauss-Newton to estimate low-rank matrices from binary data, resulting in comparable or more accurate estimates and significantly faster performance, with less sensitivity to matrix spikiness.
In 1-bit matrix completion, the aim is to estimate an underlying low-rank matrix from a partial set of binary observations. We propose a novel method for 1-bit matrix completion called Majorization-Minimization Gauss-Newton (MMGN). Our method is based on the majorization-minimization principle, which converts the original optimization problem into a sequence of standard low-rank matrix completion problems. We solve each of these sub-problems by a factorization approach that explicitly enforces the assumed low-rank structure and then apply a Gauss-Newton method. Using simulations and a real data example, we illustrate that in comparison to existing 1-bit matrix completion methods, MMGN outputs comparable if not more accurate estimates. In addition, it is often significantly faster, and less sensitive to the spikiness of the underlying matrix. In comparison with three standard generic optimization approaches that directly minimize the original objective, MMGN also exhibits a clear computational advantage, especially when the fraction of observed entries is small.