Fast Nonnegative Matrix/Tensor Factorization Based on Low-Rank Approximation

Nonnegative matrix factorization (NMF) algorithms often suffer from slow convergence speed due to the nonnegativity constraints, especially for large-scale problems. Low-rank approximation methods such as principle component analysis (PCA) are widely used in matrix factorizations to suppress noise, reduce computational complexity and memory requirements. However, they cannot be applied to NMF directly so far as they result in factors with mixed signs. In this paper, low-rank approximation is introduced to NMF (named lraNMF), which is not only able to reduce the computational complexity of NMF algorithms significantly, but also suppress bipolar noise. In fact, the new update rules are typically about M/R times faster than traditional ones of NMF, here M is the number of observations and R is the low rank of latent factors. Therefore lraNMF is particularly efficient in the case where R << M, which is the general case in NMF. The proposed update rules can also be incorporated into most existing NMF algorithms straightforwardly as long as they are based on Euclidean distance. Then the concept of lraNMF is generalized to the tensor field to perform a fast sequential nonnegative Tucker decomposition (NTD). By applying the proposed methods, the practicability of NMF/NTD is significantly improved. Simulations on synthetic and real data show the validity and efficiency of the proposed approaches.