Computing a nonnegative matrix factorization -- provably
The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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) · neural information processing systems · Cited by 9,968
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
Document clustering based on non-negative matrix factorization
Xu, W., Liu, X., & Gong, Y. (2003) · Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval · doi:10.1145/860435.860485 · Cited by 1,860
A Decision Method for Elementary Algebra and Geometry
Tarski, A. (1998) · Texts and Monographs in Symbolic Computation · doi:10.1007/978-3-7091-9459-1_3 · Cited by 1,643
Complexity and real computation
(1998) · Choice Reviews Online · doi:10.5860/choice.35-6275c · Cited by 1,228
A Decision Method for Elementary Algebra and Geometry
Tarski, A., & McKinsey, J. C. C. (1951) · University of California Press eBooks · doi:10.1525/9780520348097 · Cited by 1,206
Impagliazzo, R., & Paturi, R. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1727 · Cited by 1,002
Self Modeling Curve Resolution
Lawton, W. H., & Sylvestre, E. A. (1971) · Technometrics · doi:10.1080/00401706.1971.10488823 · Cited by 924
When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?
Donoho, D. L., & Stodden, V. (2004) · doi:10.7916/d88d05n7 · Cited by 685
On the Complexity of Nonnegative Matrix Factorization
Vavasis, S. A. (2010) · SIAM Journal on Optimization · doi:10.1137/070709967 · Cited by 588
A New Decision Method for Elementary Algebra
Seidenberg, A. (1954) · Annals of Mathematics · doi:10.2307/1969640 · Cited by 584
Latent Semantic Indexing: A Probabilistic Analysis
Papadimitriou, C. H., Raghavan, P., Tamaki, H., & Vempala, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1711 · Cited by 556
Solving systems of polynomial inequalities in subexponential time
Grigor'ev, D. Y., & Vorobjov, N. (1988) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(88)80005-1 · Cited by 368
On the possibility of faster SAT algorithms
Pǎtraşcu, M., & Williams, R. (2010) · Cited by 164
Recommendation systems: a probabilistic analysis
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743517 · Cited by 105
Color categories revealed by non-negative matrix factorization of Munsell color spectra
Buchsbaum, G., & Bloch, O. G. (2002) · Vision Research · doi:10.1016/s0042-6989(01)00303-0 · Cited by 76
Review of "Complexity and real computation" by Blum, Cucker, Shub, and Smale. Springer-Verlag.
McNicholl, T. H. (2001) · ACM SIGACT News · doi:10.1145/504192.1005765 · Cited by 68
Using mixture models for collaborative filtering
Kleinberg, J. M., & Sandler, M. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.04.013 · Cited by 40
Recommendation Systems: A Probabilistic Analysis
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1757 · Cited by 40
Alon, N., & Onn, S. (1999) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(98)00142-5 · Cited by 27
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
“Putting together the above estimates for the case w (cid:54) = 0 , we obtain Hence for all w , we can take the 1 5 √ 2 π as the lower bound, completing the proof.”
Method
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
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.