document: Fast coordinate descent methods with variable selection for non-negative matrix factorization Nonnegative Matrix Factorization ( NMF ) is an effective dimension reduction method for non-negative dyadic data , and has proven to be useful in many areas , such as text mining , bioinformatics and image processing . NMF is usually formulated as a constrained non-convex optimization problem , and many algorithms have been developed for solving it . Recently , a coordinate descent method , called FastHals , has been proposed to solve least squares NMF and is regarded as one of the state-of-the-art techniques for the problem . In this paper , we first show that FastHals has an inefficiency in that it uses a cyclic coordinate descent scheme and thus , performs unneeded descent steps on unimportant variables . We then present a variable selection scheme that uses the gradient of the objective function to arrive at a new coordinate descent method . Our new method is considerably faster in practice and we show that it has theoretical convergence guarantees . Moreover when the solution is sparse , as is often the case in real applications , our new method benefits by selecting important variables to update more often , thus resulting in higher speed . As an example , on a text dataset RCV1 , our method is 7 times faster than FastHals , and more than 15 times faster when the sparsity is increased by adding an L1 penalty . We also develop new coordinate descent methods when error in NMF is measured by KL-divergence by applying the Newton method to solve the one-variable sub-problems . Experiments indicate that our algorithm for minimizing the KL-divergence is faster than the Lee & Seung multiplicative rule by a factor of 10 on the CBCL image dataset .
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O