2021/03/02 by Moses Charikar, Lunjia Hu, Charikar, Moses +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.2103.01398
26 pages, 5 figures. To be published in AISTATS 2021. Font size increased
arxiv created 2021/03/07 · arxiv updated 2021/03/09
In the non-negative matrix factorization (NMF) problem, the input is an m× n matrix M with non-negative entries and the goal is to factorize it as M≈ AW. The m× k matrix A and the k× n matrix W are both constrained to have non-negative entries. This is in contrast to singular value decomposition, where the matrices A and W can have negative entries but must satisfy the orthogonality constraint: the columns of A are orthogonal and the rows of W are also orthogonal. The orthogonal non-negative matrix factorization (ONMF) problem imposes both the non-negativity and the orthogonality constraints, and previous work showed that it leads to better performances than NMF on many clustering tasks. We give the first constant-factor approximation algorithm for ONMF when one or both of A and W are subject to the orthogonality constraint. We also show an interesting connection to the correlation clustering problem on bipartite graphs. Our experiments on synthetic and real-world data show that our algorithm achieves similar or smaller errors compared to previous ONMF algorithms while ensuring perfect orthogonality (many previous algorithms do not satisfy the hard orthogonality constraint).