Volume 36, pp. 54-82, 2009-2010.
Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization
Lixing Han, Michael Neumann, and Upendra Prasad
Abstract
The Nonnegative Matrix Factorization (NMF) technique has been used in many areas of
science, engineering, and technology. In this paper, we propose four algorithms for
solving the nonsmooth nonnegative matrix factorization (nsNMF) problems. The nsNMF
uses a smoothing parameter to control the sparseness in its matrix
factors and it reduces to the original NMF if . Each of our algorithms
alternately solves a nonnegative linear least squares subproblem in matrix form using
a projected Barzilai–Borwein method with a nonmonotone line search or no line search.
We have tested and compared our algorithms with the projected gradient method of Lin
on a variety of randomly generated NMF problems. Our numerical results show that three
of our algorithms, namely, APBB1, APBB2, and APBB3, are significantly faster than
Lin's algorithm for large-scale, difficult, or exactly factorable NMF problems in
terms of CPU time used. We have also tested and compared our APBB2 method with the
multiplicative algorithm of Lee and Seung and Lin's algorithm for solving the nsNMF
problem resulted from the ORL face database using both and .
The experiments show that when is used, the APBB2 method can produce
sparse basis images and reconstructed images which are comparable to the ones by
the Lin and Lee–Seung methods in considerably less time. They also show that the
APBB2 method can reconstruct better quality images and obtain sparser basis images
than the methods of Lee–Seung and Lin when each method is allowed to run for a short
period of time. Finally, we provide a numerical comparison between the APBB2 method
and the Hierarchical Alternating Least Squares (HALS)/Rank-one Residue Iteration
(RRI) method, which was recently proposed by Cichocki, Zdunek, and Amari and by Ho,
Van Dooren, and Blondel independently.
Full Text (PDF) [1.1 MB],
BibTeX
Key words
nonnegative matrix factorization, smoothing matrix, nonnegative least squares problem, projected Barzilai–Borwein method, nonmonotone line search.
AMS subject classifications
15A48, 15A23, 65F30, 90C30