On the Complexity of Nonnegative Matrix Factorization
SIAM Journal on OptimizationPublished 16 October 2009
Stephen A. Vavasis
Citations585
SJR quartileQ1
SJR score1.39
SNIP1.79
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An exact version of nonnegative matrix factorization is defined and it is established that it is equivalent to a problem in polyhedral combinatorics; it is NP-hard; and that a polynomial-time local search heuristic exists.
Abstract
Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases, and other information retrieval and clustering applications. The problem is most naturally posed as continuous optimization. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (i) that it is equivalent to a problem in polyhedral combinatorics; (ii) that it is NP-hard; and (iii) that a polynomial-time local search heuristic exists.
Keywords
Computer ScienceEngineering
NatureLearning the parts of objects by non-negative matrix factorization
14,055 Citations1999Daniel D. Lee, H. Sebastian Seung
An algorithm for non-negative matrix factorization is demonstrated that is able to learn parts of faces and semantic features of text and is in contrast to other methods that learn holistic, not parts-based, representations.
arXiv (Cornell University)Probabilistic Latent Semantic Analysis
2,092 Citations2013Thomas Hofmann
This work proposes a widely applicable generalization of maximum likelihood model fitting by tempered EM, based on a mixture decomposition derived from a latent class model which results in a more principled approach which has a solid foundation in statistics.
Choice Reviews OnlineComplexity and real computation
1,263 Citations1998
The complexity and real computation is universally compatible with any devices to read and is available in the authors' book collection an online access to it is set as public so you can download it instantly.
BioinformaticsSparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis
909 Citations2007Hyunsoo Kim, Haesun Park
The experimental results illustrate that the proposed sparse NMF algorithm often achieves better clustering performance with shorter computing time compared to other existing NMF algorithms.
Pattern RecognitionSVD based initialization: A head start for nonnegative matrix factorization
683 Citations2007Christos Boutsidis, Efstratios Gallopoulos
Nonnegative Double Singular Value Decomposition (NNDSVD), a new method designed to enhance the initialization stage of nonnegative matrix factorization (NMF), is described and suggests that NNDSVD leads to rapid reduction of the approximation error of many NMF algorithms.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsIterative signature algorithm for the analysis of large-scale gene expression data
429 Citations2003Sven Bergmann, Jan Ihmels +1 more
It is shown analytically that for noisy expression data the proposed approach leads to better classification due to the implementation of the threshold, and argues that the method is in fact a generalization of singular value decomposition, which corresponds to the special case where no threshold is applied.
Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical PhysicsSystems of distinct representatives and linear algebra
392 Citations1967Jack Edmonds
Linear Algebra and its ApplicationsNonnegative ranks, decompositions, and factorizations of nonnegative matrices
258 Citations1993Joel E. Cohen, Uriel G. Rothblum
Nonnegative matrix factorization via rank-one downdate
33 Citations2008Michael Biggs, Ali Ghodsi +1 more
An algorithm called rank-one downdate (R1D) is proposed for computing an NMF that is partly motivated by the singular value decomposition, and establishes a theoretical result that maximizing this objective function corresponds to correctly classifying articles in a nearly separable corpus.
Using Rank-One Biclusters to Classify Microarray Data
11 Citations2007Nasimeh Asgarian, Russell Greiner
This paper proposes a novel algorithm for learning a microarray classier by reducing the dimensionality of the data matrix using biclusters, where each bicluster is a subset of genes andA subset of samples whose expression values have similar patterns.