Using underapproximations for sparse nonnegative matrix factorization
From MaRDI portal
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.
Recommendations
- Non-negative matrix factorization with sparseness constraints
- Sparse and unique nonnegative matrix factorization through data preprocessing
- Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
- Learning sparse representations by non-negative matrix factorization and sequential cone programming
- Nonnegative matrix factorization
Cites work
- scientific article; zbMATH DE number 3894826 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Direct Formulation for Sparse PCA Using Semidefinite Programming
- Algorithms and applications for approximate nonnegative matrix factorization
- Document clustering using nonnegative matrix factorization
- Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization
- Learning sparse representations by non-negative matrix factorization and sequential cone programming
- Learning the parts of objects by non-negative matrix factorization
- Non-negative matrix factorization with sparseness constraints
- Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
- Nonnegative matrix factorization for spectral data analysis
- Nonnegativity constraints in numerical analysis
- On the complexity of nonnegative matrix factorization
- Projected Gradient Methods for Nonnegative Matrix Factorization
- SVD based initialization: A head start for nonnegative matrix factorization
- The maximum edge biclique problem is NP-complete
- Two ``well-known properties of subgradient optimization
Cited in
(22)- Graph dual regularization non-negative matrix factorization for co-clustering
- A simple filter for detecting low-rank submatrices
- Singular value analysis of linear maps under conic constraints
- Integer matrix approximation and data mining
- A unified statistical approach to non-negative matrix factorization and probabilistic latent semantic indexing
- A quasi-likelihood approach to nonnegative matrix factorization
- Heuristics for exact nonnegative matrix factorization
- On the complexity of robust PCA and \(\ell_1\)-norm low-rank matrix approximation
- Efficient nonnegative matrix factorization via projected Newton method
- Conic optimization-based algorithms for nonnegative matrix factorization
- Algorithms for approximate subtropical matrix factorization
- A multilevel approach for nonnegative matrix factorization
- A nonlinear matrix decomposition for mining the zeros of sparse data
- Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
- Sparse and unique nonnegative matrix factorization through data preprocessing
- Low-rank matrix factorization with multiple hypergraph regularizer
- Multiple graph regularized nonnegative matrix factorization
- Computing symmetric nonnegative rank factorizations
- A clustering approach to constrained binary matrix factorization
- Nonlinear nonnegative matrix factorization based on Mercer kernel construction
- Sparse nonnegative matrix underapproximation and its application to hyperspectral image analysis
- Singular value problems under nonnegativity constraints
This page was built for publication: Using underapproximations for sparse nonnegative matrix factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q962750)
