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.