Randomized Algorithms for Symmetric Nonnegative Matrix Factorization
Koby Hayashi Sinan G. Aksoy Grey Ballard Haesun Park
Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data
analysis and machine learning that approximates a symmetric matrix with a
product of a nonnegative, low-rank matrix and its transpose. To design faster
and more scalable algorithms for SymNMF we develop two randomized algorithms
for its computation. The first algorithm uses randomized matrix sketching to
compute an initial low-rank input matrix and proceeds to use this input to
rapidly compute a SymNMF. The second algorithm uses randomized leverage score
sampling to approximately solve constrained least squares problems. Many
successful methods for SymNMF rely on (approximately) solving sequences of
constrained least squares problems. We prove theoretically that leverage score
sampling can approximately solve nonnegative least squares problems to a chosen
accuracy with high probability. Finally we demonstrate that both methods work
well in practice by applying them to graph clustering tasks on large real world
data sets. These experiments show that our methods approximately maintain
solution quality and achieve significant speed ups for both large dense and
large sparse problems.