2010/09/30 by Nicolas Gillis, François Glineur · 30 citations
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Applied mathematics #Artificial intelligence #Combinatorics #Computer science #Convergence (economics) #Face and Expression Recognition #Factorization #Image (mathematics) #Image Retrieval and Classification Techniques #Least-squares function approximation #Mathematical analysis #Mathematics #Matrix (chemical analysis) #Matrix decomposition #Multiplicative function #Non-negative matrix factorization #Nonnegative matrix #Rank (graph theory) #Representation (politics) #Simple (philosophy) #Statistics #Symmetric matrix #cs.NA #math.NA #math.OC
paper · pdf · doi:10.1016/j.cam.2011.10.002
published in Journal of Computational and Applied Mathematics 236(7), 1708-1723 (Elsevier BV) · 23 pages, 10 figures. Section 6 added discussing limitations of the method. Accepted in Journal of Computational and Applied Mathematics
arxiv created 2011/10/04 · openalex publication_date 2011/10/17 · arxiv updated 2012/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Nonnegative Matrix Factorization (NMF) is the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices and has been shown to be particularly useful in many applications, e.g., in text mining, image processing, computational biology, etc. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. A simple multilevel strategy is described and is experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets.