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.