Fast Rank Reduction for Non-negative Matrices via Mean Field Theory
This addresses a computational bottleneck in matrix factorization for applications like data compression or dimensionality reduction, though it appears incremental as it builds on existing NMF methods.
The paper tackles the problem of efficiently reducing the rank of non-negative matrices by proposing a method with quadratic time complexity, achieving competitive low-rank approximation error compared to NMF and lraNMF on synthetic and real-world datasets.
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.