Using Underapproximations for Sparse Nonnegative Matrix Factorization

Abstract

Nonnegative Matrix Factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc. We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs. We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard Sparse Nonnegative Matrix Factorization techniques.

Version 2 removed the section about convex reformulations, which was not central to the development of our main results; added material to the introduction; added a review of previous related work (section 2.3); completely rewritten the last part (section 4) to provide extensive numerical results supporting our claims. Accepted in J. of Pattern Recognition

References in corpus (3)

• Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization
• Nonnegative Factorization and The Maximum Edge Biclique Problem
• Nuclear norm minimization for the planted clique and biclique problems

Cited by in corpus (14)

• Low-Rank Matrix Approximation with Weights or Missing Data is NP-hard
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Improved SVD-based Initialization for Nonnegative Matrix Factorization using Low-Rank Correction
• Nonnegative Factorization and The Maximum Edge Biclique Problem
• Heuristics for Exact Nonnegative Matrix Factorization
• On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation
• Sequential Dimensionality Reduction for Extracting Localized Features
• Embedded Deep Regularized Block HSIC Thermomics for Early Diagnosis of Breast Cancer
• Finding approximately rank-one submatrices with the nuclear norm and l1 norm
• How to Fake Multiply by a Gaussian Matrix
• On Defining SPARQL with Boolean Tensor Algebra
• Conic-Optimization Based Algorithms for Nonnegative Matrix Factorization
• Non-negative matrix underapproximation as optimal frequency band selector
• Algorithms for Approximate Subtropical Matrix Factorization