  We propose an efficient matrix rank reduction method for non-negative
matrices, whose time complexity is quadratic in the number of rows or columns
of a matrix. Our key insight is to formulate rank reduction as a mean-field
approximation by modeling matrices via a log-linear model on structured sample
space, which allows us to solve the rank reduction as convex optimization. The
highlight of this formulation is that the optimal solution that minimizes the
KL divergence from a given matrix can be analytically computed in a closed
form. We empirically show that our rank reduction method is faster than NMF and
its popular variant, lraNMF, while achieving competitive low rank approximation
error on synthetic and real-world datasets.
