A Quantum-inspired Classical Algorithm for Separable Non-negative Matrix
Factorization
Abstract
Non-negative Matrix Factorization (NMF) asks to
decompose a (entry-wise) non-negative matrix into
the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In
order to overcome this issue, separability assumption is introduced which assumes all data points
are in a conical hull. This assumption makes NMF
tractable and is widely used in text analysis and image processing, but still impractical for huge-scale
datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new
classical algorithm for separable NMF problem. Our
new algorithm runs in polynomial time in the rank
and logarithmic in the size of input matrices, which
achieves an exponential speedup in the low-rank
setting