A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization
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.
Mon 14 MarDisplayed time zone: Belfast change
14:20 - 16:00 | |||
14:20 25mTalk | Articulation Point Guided Redundancy Elimination for Betweenness Centrality Main conference Lei Wang Institute of Computing Technology, Chinese Academy of Science, Fan Yang Institute of Computing Technology, Chinese Academy of Science, Liangji Zhuang Institute of Computing Technology, Chinese Academy of Science, Huimin Cui Institute of Computing Technology, Chinese Academy of Sciences, Fang Lv Institute of Computing Technology, Chinese Academy of Sciences, Xiaobing Feng ICT CAS Link to publication DOI | ||
14:45 25mTalk | Multi-Core On-The-Fly SCC Decomposition Main conference Vincent Bloemen University of Twente, Alfons Laarman Vienna University of Technology, Jaco van de Pol University of Twente Link to publication DOI | ||
15:10 25mTalk | A High-Performance Parallel Algorithm for Nonnegative Matrix Factorization Main conference Ramakrishnan Kannan Georgia Institute of Technology, Grey Ballard Sandia National Laboratories, Haesun Park Georgia Institute of Technology Link to publication DOI | ||
15:35 25mTalk | Autogen: Automatic Discovery of Cache-Oblivious Parallel Recursive Algorithms for Solving Dynamic Programs Main conference Rezaul Chowdhury Stony Brook University, Pramod Ganapathi Stony Brook University, Jesmin Jahan Tithi Intel, CA, USA, Charles Bachmeier MIT, Bradley Kuszmaul MIT, Charles E. Leiserson MIT, Armando Solar-Lezama MIT, Yuan Tang Fudan University Link to publication DOI |