Abstract
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 ≈ WH. NMF is a useful tool for many applications in different 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 efficient 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.
| Original language | English |
|---|---|
| Title of host publication | 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 - Proceedings |
| Publisher | Association for Computing Machinery |
| ISBN (Electronic) | 9781450340922 |
| DOIs | |
| State | Published - Feb 27 2016 |
| Event | 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 - Barcelona, Spain Duration: Mar 12 2016 → Mar 16 2016 |
Publication series
| Name | Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP |
|---|---|
| Volume | 12-16-March-2016 |
Conference
| Conference | 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016 |
|---|---|
| Country/Territory | Spain |
| City | Barcelona |
| Period | 03/12/16 → 03/16/16 |
Funding
This research was supported in part by an appointment to the Sandia National Laboratories Truman Fellowship in National Security Science and Engineering, sponsored by Sandia Corporation (a wholly owned subsidiary of Lockheed Martin Corporation) as Operator of Sandia National Laboratories under its U.S. Department of Energy Contract No. DE-AC04-94AL85000. This research used resources of the National Energy Research Scientific Computing Center, a DOE Office of Science User Facility supported by the Office of Science of the U.S. Department of Energy under Contract No. DE-AC02-05CH11231. Partial funding for this work was also provided by AFOSR Grant FA9550-13-1-0100, National Science Foundation (NSF) grants IIS-1348152 and ACI-1338745, Defense Advanced Research Projects Agency (DARPA) XDATA program grant FA8750-12-2-0309. We also thank NSF for the travel grant to present this work in the conference through the grant CCF-1552229. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflectthe views of the USDOE, NERSC, AFOSR, NSF or DARPA.