Alternating projected Barzilai-Borwein methods for Nonnegative Matrix Factorization

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 θ Ε [0, 1] to control the sparseness in its matrix factors and it reduces to the original NMF if θ = 0. 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 θ = 0 and θ = 0.7. The experiments show that when θ = 0.7 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.