Beyond the Worst-Case Analysis of Algorithms
Topic Models and Nonnegative Matrix Factorization
Publication
, Chapter
Ge, R; Moitra, A
January 1, 2021
In this chapter, we introduce nonnegative matrix factorization and topic modeling. We will see that there is a natural structural assumption called separability that allows us to circumvent the worst-caseNP-hardness results for nonnegative matrix factorization. We will devise a simple algorithm for separable nonnegative matrix factorization and apply it to the problem of learning the parameters of a topic model. Finally we will give an alternative algorithm for topic modeling based on low-rank tensor decomposition.
Duke Scholars
Citation
APA
Chicago
ICMJE
MLA
NLM
Ge, R., & Moitra, A. (2021). Topic Models and Nonnegative Matrix Factorization. In Beyond the Worst-Case Analysis of Algorithms (pp. 445–464). https://doi.org/10.1017/9781108637435.026
Ge, R., and A. Moitra. “Topic Models and Nonnegative Matrix Factorization.” In Beyond the Worst-Case Analysis of Algorithms, 445–64, 2021. https://doi.org/10.1017/9781108637435.026.
Ge R, Moitra A. Topic Models and Nonnegative Matrix Factorization. In: Beyond the Worst-Case Analysis of Algorithms. 2021. p. 445–64.
Ge, R., and A. Moitra. “Topic Models and Nonnegative Matrix Factorization.” Beyond the Worst-Case Analysis of Algorithms, 2021, pp. 445–64. Scopus, doi:10.1017/9781108637435.026.
Ge R, Moitra A. Topic Models and Nonnegative Matrix Factorization. Beyond the Worst-Case Analysis of Algorithms. 2021. p. 445–464.