Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method
Top Cited Papers
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 30 (2), 713-730
- https://doi.org/10.1137/07069239x
Abstract
Nonnegative matrix factorization (NMF) determines a lower rank approximation of a matrix $A \in \mathbb{R}^{m \times n} \approx WH$ where an integer $k \ll \min(m,n)$ is given and nonnegativity is imposed on all components of the factors $W \in \mathbb{R}^{m \times k}$ and $H \in \mathbb{R}^{k \times n}$. NMF has attracted much attention for over a decade and has been successfully applied to numerous data analysis problems. In applications where the components of the data are necessarily nonnegative, such as chemical concentrations in experimental results or pixels in digital images, NMF provides a more relevant interpretation of the results since it gives nonsubtractive combinations of nonnegative basis vectors. In this paper, we introduce an algorithm for NMF based on alternating nonnegativity constrained least squares (NMF/ANLS) and the active set–based fast algorithm for nonnegativity constrained least squares with multiple right-hand side vectors, and we discuss its convergence properties and a rigorous convergence criterion based on the Karush–Kuhn–Tucker (KKT) conditions. In addition, we also describe algorithms for sparse NMFs and regularized NMF. We show how we impose a sparsity constraint on one of the factors by $L_1$-norm minimization and discuss its convergence properties. Our algorithms are compared to other commonly used NMF algorithms in the literature on several test data sets in terms of their convergence behavior.
Keywords
This publication has 16 references indexed in Scilit:
- Algorithms and applications for approximate nonnegative matrix factorizationComputational Statistics & Data Analysis, 2007
- Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysisBioinformatics, 2007
- Improving molecular cancer class discovery through sparse non-negative matrix factorizationBioinformatics, 2005
- Multi-way clustering of microarray data using probabilistic sparse matrix factorizationBioinformatics, 2005
- Metagenes and molecular pattern discovery using matrix factorizationProceedings of the National Academy of Sciences of the United States of America, 2004
- Subsystem Identification Through Dimensionality Reduction of Large-Scale Gene Expression DataGenome Research, 2003
- On the convergence of the block nonlinear Gauss–Seidel method under convex constraintsOperations Research Letters, 2000
- Learning the parts of objects by non-negative matrix factorizationNature, 1999
- Molecular Classification of Cancer: Class Discovery and Class Prediction by Gene Expression MonitoringScience, 1999
- A fast non-negativity-constrained least squares algorithmJournal of Chemometrics, 1997