The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Computing a nonnegative matrix factorization -- provably
Abstract
The Nonnegative Matrix Factorization (NMF) problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where the factorization is computed using a variety of local search heuristics. Vavasis recently proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time. Consider a nonnegative m x n matrix $M$ and a target inner-dimension r. Our results are the following: - We give a polynomial-time algorithm for exact and approximate NMF for every constant r. Indeed NMF is most interesting in applications precisely when r is small. We complement this with a hardness result, that if exact NMF can be solved in time (nm)o(r), 3-SAT has a sub-exponential time algorithm. Hence, substantial improvements to the above algorithm are unlikely. - We give an algorithm that runs in time polynomial in n, m and r under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
Indexing by latent semantic analysis
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9 · Cited by 12,751
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · Cited by 7,952
Independent Component Analysis
(2004) · Independent Component Analysis · doi:10.7551/mitpress/3717.003.0014 · Cited by 7,903
Paatero, P., & Tapper, U. (1994) · Environmetrics · doi:10.1002/env.3170050203 · Cited by 6,023
Independent Component Analysis
Hyvärinen, A., Karhunen, J., & Oja, E. (2001) · Wiley eBooks · doi:10.1002/0471221317 · Cited by 5,007
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Seung, D., & Lee, L.-W. (2001) · Cited by 4,753
Non-negative matrix factorization with sparseness constraints
Hoyer, P. O. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408058 · Cited by 2,591
Probabilistic Latent Semantic Analysis
Hofmann, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6705 · Cited by 2,047
Cited by
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
A Signal Processing Perspective on Hyperspectral Unmixing: Insights from Remote Sensing
Ma, W.-K., Bioucas-Dias, J. M., Chan, T.-H., Gillis, N., Gader, P., Plaza, A. J., Ambikapathi, A., & Chi, C.-Y. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2279731 · Cited by 456
Learning Topic Models -- Going beyond SVD
Arora, S., Ge, R., & Moitra, A. (2012) · 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.49 · Cited by 302
Self-citationFast and Robust Recursive Algorithmsfor Separable Nonnegative Matrix Factorization
Gillis, N., & Vavasis, S. A. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.226 · Cited by 261
Complete Dictionary Recovery Over the Sphere I: Overview and the Geometric Picture
Sun, J., Qu, Q., & Wright, J. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2016.2632162 · Cited by 213
Metadata
- Authors
- Arora, S., Ge, R., Kannan, R., & Moitra, A.
- Venue
- Proceedings of the forty-fourth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2012-05-19
- Pages
- 145-162
- OpenAlex
- W2111604514
- Cited by
- 280
- References
- 28
- FWCI
- 24.79
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Computing a nonnegative matrix factorization -- provably. https://app.cochat.ai/papers/10.1145/2213977.2213994
- The paper
- Arora, S., Ge, R., Kannan, R., & Moitra, A. (2012). Computing a nonnegative matrix factorization -- provably. Proceedings of the forty-fourth annual ACM symposium on Theory of computing. https://doi.org/10.1145/2213977.2213994
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.