A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization

作者：Kannan Ramakrishnan^*; Ballard Grey; Park Haesun

来源：ACM Sigplan Notices, 2016, 51(8): 99-109.

DOI：10.1145/2851141.2851152

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors W and H, for the given input matrix A, such that A approximate to WH. NMF is a useful tool for many applications in di ff erent domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of e ffi cient distributed algorithms to solve the problem for big data sets.
We propose a high-performance distributed-memory parallel algorithm that computes the factorization by iteratively solving alternating non-negative least squares (NLS) subproblems for W and H. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). As opposed to previous implementations, our algorithm is also flexible: (1) it performs well for both dense and sparse matrices, and (2) it allows the user to choose any one of the multiple algorithms for solving the updates to low rank factors W and H within the alternating iterations. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements.

• 出版日期2016-8