Non-negative matrix factorization algorithms generally improve topic model fits Authors: Peter Carbonetto, Abhishek Sarkar, Zihao Wang, Matthew Stephens Published: 2026 ABSTRACT In an effort to develop topic modeling methods that can be quickly applied to large data sets, we revisit the problem of maximum-likelihood estimation in topic models. It is known, at least informally, that maximum-likelihood estimation in topic models is closely related to non-negative matrix factorization (NMF). Yet, to our knowledge, this relationship has not been exploited previously to fit topic models. We show that recent advances in NMF optimization methods can be leveraged to fit topic models very efficiently, often resulting in much better fits and in less time than existing algorithms for topic models. We also formally make the connection between the NMF optimization problem and maximum-likelihood estimation for the topic model, and using this result we show that the expectation maximization (EM) algorithm for the topic model is essentially the same as the classic multiplicative updates for NMF. Our methods are implemented in the R package “fastTopics”. Introduction The focus of this paper is the problem of computing maximum-likelihood estimates (MLEs) of the parameters in a topic model given an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \times m$$\end{document}n×m matrix of counts. Instead of directly computing the MLE for the topic model, we instead propose to solve a similar problem with much simpler constraints on the parameters: optimizing a non-negative matrix factorization (NMF) based on a Poisson model of the data (Lee and Seung (1999, 2001); Cichocki et al. (2011); Dhillon and Sra (2005); Févotte and Idier (2011); Hien and Gillis (2021)). Despite the fact that the topic model and Poisson NMF are well known to be closely related (Buntine (2002); Buntine and Jakulin (2006); Canny (2004); Ding et al. (2008); Faleiros et al. (2016); Gaussier and Goutte (2005); Gillis (2021); Zhou et al. (2012)), as far as we are aware this relationship has not been previously exploited for fitting topic models. An intuition for the advantage of this approach is that the Poisson NMF optimization problem lacks the “sum-to-one” constraints, which complicate optimization. However, not all Poisson NMF algorithms exploit this benefit. Indeed, the traditional way to solve Poisson NMF—the “multiplicative updates” of Lee and Seung (2001)—is equivalent to expectation maximization (EM) (Cemgil 2009), and, as we show, is closely related to the EM algorithms traditionally used to fit topic models. (In fact, we show that these algorithms are mostly the same except for the order in which the operations are performed.) Therefore, the Poisson NMF multiplicative updates are expected to experience the same issues as EM, and this is indeed borne out by our experiments. In contrast, other recently developed algorithms for solving Poisson NMF based on co-ordinate descent (CD) (Hsieh and Dhillon 2011; Lin and Boutros 2020) do not have an existing counterpart for topic models. It has been shown that CD algorithms can greatly outperform the multiplicative updates for Poisson NMF (Hien and Gillis 2021). And here we show that CD algorithms can also be leveraged to fit topic models very efficiently, often resulting in much better fits and in less time than the existing algorithms for topic models. A maximum-likelihood approach to topic modeling is not new, of course; one of the very first papers on topic modeling, Hofmann (1999), used a simple EM algorithm to obtain MLEs under the topic model. EM, however, can be very slow to converge to a local maximum of the likelihood (Redner and Walker (1984); Ma et al. (2000); Dwivedi et al. (2020); Kunstner et al. (2021); Zhou et al. (2011); Varadhan and Roland (2008); Henderson and Varadhan (2019)). The slow convergence of EM is sometimes viewed as a feature, not a bug: “early stopping” has been shown, both anecdotally and in theory, to result in parameter estimates that better generalize to test sets—that is, early stopping can implicitly regularize the MLEs (Ali et al. 2019; Gunasekar et al. 2017). We show however that this slow convergence can also sometimes cause the EM to get “stuck” in areas of the likelihood that are far away from a local maximum, resulting in very poor parameter estimates. We also show that the fast NMF algorithms can very quickly “rescue” the EM estimates, resulting in parameter estimates that are very different from and much better than the estimates produced by EM. The maximum-likelihood approach we study in this paper contrasts with the much more widely used variational inference approach for topic models, i.e., latent Dirichlet allocation (Blei et al. (2003); Teh et al. (2007); Asuncion et al. (2009)). The benefit of variational inference is that it produces approximate posterior estimates of the model parameters, which can help to address overfitting, stabilize parameter estimates, and increase accuracy. However, the underlying computations for variational inference are more complex, making the algorithms slower and more challenging to apply to very large data sets. For these reasons, “online” variational inference algorithms have been developed (Hoffman et al. 2010; Sato 2001). But online learning algorithms bring their own challenges; for example, unlike conventional optimization algorithms, they do not guarantee that the objective will improve at each iteration, and the results of online learning are often sensitive to parameter tuning. (Markov chain Monte Carlo algorithms for posterior inference in topic models have also been used in the past e.g., Griffiths and Steyvers (2004), but MCMC is typically more computationally burdensome than variational inference.) Therefore, on balance, maximum-likelihood estimation remains an attractive option for many large data sets, especially when maximum-likelihood estimation is implemented using fast NMF algorithms, as we show here. Indeed, reframing the problem of fitting a topic model as an NMF optimization problem has already enabled us and others to efficiently fit topic models to very large single-cell data sets, in some cases with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n, m \ge \text{100,000 }$$\end{document}n,m≥100,000 (Chirichella et al. 2025; Dey et al. 2017; González-Blas et al. 2019; Carbonetto et al. 2023; Umans and Gilad 2025; Meir et al. 2025; Gao et al. 2024; Popp et al. 2024; Liang et al. 2024; Zhao et al. 2024; Housman et al. 2022; Hung et al. 2022; Rhodes et al. 2022; Bastide et al. 2022). The numerical experiments in this paper include two single-cell data sets, and demonstrate the benefits of applying fast NMF algorithms to fit topic models for single-cell data sets. The algorithms for fitting topic models and Poisson NMF described in this paper are implemented in an R package, fastTopics, which is available on CRAN (https://cran.r-project.org/package=fastTopics) and on GitHub (https://github.com/stephenslab/fastTopics/). Poisson NMF and the multinomial topic model In the following, we provide side-by-side descriptions of the topic model and Poisson NMF to highlight their close connection. While formal and informal connections between these two models have been made previously (Buntine (2002); Buntine and Jakulin (2006); Canny (2004); Ding et al. (2008); Faleiros et al. (2016); Gaussier and Goutte (2005); Zhou et al. (2012)). We provide a simple and more general result relating the likelihoods of the two models (Lemma 1), which we view as a more fundamental result underlying previous results.1 Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{X}\in \textbf{R}_{+}^{n \times m}$$\end{document}X∈R+n×m denote an \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \times m$$\end{document}n×m matrix of observed counts \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_{ij}$$\end{document}xij. For example, when analyzing text documents, n is the number of documents, m is the number of unique terms, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_{ij}$$\end{document}xij is the number of times term j occurs in document i. Both Poisson NMF and the topic model can be seen as fitting different—but closely related—models of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{X}$$\end{document}X. The Poisson NMF model has parameters that are non-negative matrices, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H} \in \textbf{R}_{+}^{n \times K}$$\end{document}H∈R+n×K and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W} \in \textbf{R}_{+}^{m \times K}$$\end{document}W∈R+m×K, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{R}_{+}^{r \times c}$$\end{document}R+r×c denotes the set of non-negative, real matrices with r rows and c columns. Given a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K \ge 1$$\end{document}K≥1, the Poisson NMF model is1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} x_{ij}&\mid \textbf{H}, \textbf{W} \sim \textrm{Pois}(\lambda _{ij}) \\ \lambda _{ij}&= (\textbf{HW}^T)_{ij} = \sum _{k=1}^K h_{ik} w_{jk}, \end{aligned} \end{aligned}$$\end{document}xij∣H,W∼Pois(λij)λij=(HWT)ij=∑k=1Khikwjk,where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_{ij}, w_{jk}$$\end{document}hij,wjk denote elements of matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{Pois}(\lambda )$$\end{document}Pois(λ) denotes the Poisson distribution with rate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}λ. Poisson NMF can be viewed as a rank-K matrix factorization by noting that (1) implies \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E[\textbf{X}] = \textbf{HW}^T$$\end{document}E[X]=HWT. So fitting a Poisson NMF essentially seeks values of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{X}\approx \textbf{HW}^T$$\end{document}X≈HWT.2 Computing an MLE for the Poisson NMF model reduces to the following bound-constrained optimization problem:2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \ell (\textbf{X}; \textbf{H}, \textbf{W}) \\ \text{ subject } \text{ to } & \textbf{H} \ge {{\boldsymbol{0}}}, \textbf{W} \ge {{\boldsymbol{0}}}, \end{array} \end{aligned}$$\end{document}minimizeℓ(X;H,W)subjecttoH≥0,W≥0,in which the objective function is3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \ell (\textbf{X}; \textbf{H}, \textbf{W})~{:}{=}&\; \phi (\textbf{X}; \textbf{H}, \textbf{W}) + \Vert \textbf{H} \textbf{W}^T \Vert _{1,1} \end{aligned}$$\end{document}ℓ(X;H,W):=ϕ(X;H,W)+‖HWT‖1,14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \phi (\textbf{X}; \textbf{H}, \textbf{W})~{:}{=}&\; -\sum _{i=1}^n \sum _{j=1}^m x_{ij} \log {{\boldsymbol{h}}}_i^T {{\boldsymbol{w}}}_j, \end{aligned}$$\end{document}ϕ(X;H,W):=-∑i=1n∑j=1mxijloghiTwj,where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Vert \textbf{A}\Vert _{1,1} = \sum _{i = 1}^n \sum _{j = 1}^m |a_{ij}|$$\end{document}‖A‖1,1=∑i=1n∑j=1m|aij| is the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$L_{1,1}$$\end{document}L1,1 norm of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \times m$$\end{document}n×m matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{h}}}_i, {{\boldsymbol{w}}}_j$$\end{document}hi,wj denote, respectively, the ith row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H and the jth row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W. Like Poisson NMF, the multinomial topic model is also parameterized by two non-negative matrices, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}\in \textbf{R}_{+}^{n \times K}$$\end{document}L∈R+n×K, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}\in \textbf{R}_{+}^{m \times K}$$\end{document}F∈R+m×K, but the elements of these two matrices must satisfy additional “sum-to-one” constraints:5\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \sum _{j=1}^m f_{jk} = 1, \quad \sum _{k=1}^K l_{ik} = 1. \end{aligned}$$\end{document}∑j=1mfjk=1,∑k=1Klik=1.Most variations of the topic model, including the aspect model (Hofmann et al. 1999), probabilistic latent semantic indexing (Hofmann 2001; Hoffman et al. 2010; Hofmann 1999) and latent Dirichlet allocation (Blei et al. 2003), are based on the same basic model: a multinomial distribution of the counts. We therefore refer to this model as the multinomial topic model. Given a \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K \ge 2$$\end{document}K≥2, the multinomial topic model is6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} x_{i1}, \ldots , x_{im}&\mid \textbf{L}, \textbf{F} \sim \textrm{Multin}(t_i; \pi _{i1}, \ldots , \pi _{im}) \\ \pi _{ij}&= (\textbf{L}\textbf{F}^T)_{ij} = \sum _{k=1}^K l_{ik} f_{jk}, \end{aligned} \end{aligned}$$\end{document}xi1,…,xim∣L,F∼Multin(ti;πi1,…,πim)πij=(LFT)ij=∑k=1Klikfjk,in which \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{Multin}(n; \pi _1, \ldots , \pi _m)$$\end{document}Multin(n;π1,…,πm) is the multinomal distribution with sample size n and probabilities \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _1, \ldots , \pi _m$$\end{document}π1,…,πm, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t_i~{:}{=}\sum _{j=1}^m x_{ij}$$\end{document}ti:=∑j=1mxij. The multinomial topic model is also a matrix factorization because we have that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf{\Pi } = \textbf{L}\textbf{F}^T$$\end{document}Π=LFT, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbf{\Pi }$$\end{document}Π denotes the matrix of multinomial probabilities \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _{ij}$$\end{document}πij (Hofmann (1999); Singh and Gordon (2008); Steyvers and Griffiths (2007)). Computing an MLE for the multinomial topic model reduces to a linearly constrained optimization problem,7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \phi (\textbf{X}; \textbf{L}, \textbf{F}) \\ \text{ subject } \text{ to } & \textbf{L} {\boldsymbol{1}}_K = {\boldsymbol{1}}_n \\ & \textbf{F}^T {\boldsymbol{1}}_m = {\boldsymbol{1}}_K \\ & \textbf{L} \ge {\boldsymbol{0}}, \textbf{F} \ge {\boldsymbol{0}}, \end{array} \end{aligned}$$\end{document}minimizeϕ(X;L,F)subjecttoL1K=1nFT1m=1KL≥0,F≥0,in which \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{1}}_d = (1, \ldots , 1)^T$$\end{document}1d=(1,…,1)T denotes a column vector of ones of length d, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi $$\end{document}ϕ was defined in (4). Now we connect the Poisson non-negative matrix factorization to the multinomial topic model matrix factorization. To do so, we define a mapping between the parameter spaces for the two models (Definition 1), and then we state an equivalence between their likelihoods (Lemma 1), which leads to an equivalence in their MLEs (Corollary 1). Definition 1 (Poisson NMF to multinomial topic model reparameterization) Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{R}_{++}^d$$\end{document}R++d denote the set of positive real vectors of length d, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{R}_\textrm{row}^{r \times c}$$\end{document}Rrowr×c denote the set of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \times c$$\end{document}r×c row-normalized matrices (non-negative matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A with the property that the elements in each row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A sum to 1), and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{R}_\textrm{col}^{r \times c}$$\end{document}Rcolr×c denote the set of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \times c$$\end{document}r×c column-normalized matrices (non-negative matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A with the property that the elements in each column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A sum to 1). For \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K \ge 2$$\end{document}K≥2, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H} \in \textbf{R}_{+}^{n \times K}$$\end{document}H∈R+n×K, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W} \in \textbf{R}_{+}^{m \times K}$$\end{document}W∈R+m×K, define mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM} : \textbf{H}, \textbf{W} \mapsto \textbf{L}, \textbf{F}, {{\boldsymbol{s}}}, {{\boldsymbol{u}}}$$\end{document}PNMF-TO-MTM:H,W↦L,F,s,u, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}\in \textbf{R}_{\textrm{row}}^{n \times K}$$\end{document}L∈Rrown×K, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F} \in \textbf{R}_{\textrm{col}}^{m \times K}$$\end{document}F∈Rcolm×K, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{s}}} \in \textbf{R}_{++}^n$$\end{document}s∈R++n, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{u}}} \in \textbf{R}_{++}^K$$\end{document}u∈R++K by the following procedure: This procedure has two subroutines, defined as follows: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Rows}(\textbf{A})$$\end{document}NORMALIZE-ROWS(A) returns a vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{y}}} \in \textbf{R}_{++}^r$$\end{document}y∈R++r containing the row sums of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \times c$$\end{document}r×c matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y_i = \sum _{j=1}^c a_{ij}$$\end{document}yi=∑j=1caij, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{B} \in \textbf{R}_\textrm{row}^{r \times c}$$\end{document}B∈Rrowr×c, a row-normalized matrix with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_{ij} = a_{ij} / y_i$$\end{document}bij=aij/yi; and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Cols}(\textbf{A})$$\end{document}NORMALIZE-COLS(A) returns a vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{y}}} \in \textbf{R}_{++}^c$$\end{document}y∈R++c containing the column sums of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$y_j = \sum _{i=1}^r a_{ij}$$\end{document}yj=∑i=1raij, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{B} \in \textbf{R}_\textrm{col}^{r \times c}$$\end{document}B∈Rcolr×c, a column-normalized matrix with entries \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_{ij} = a_{ij} / y_j$$\end{document}bij=aij/yj. We also define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{diag}({{\boldsymbol{a}}})$$\end{document}diag(a) as the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \times n$$\end{document}n×n diagonal matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A with diagonal entries given by the elements of vector \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{a}}}$$\end{document}a. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Rows}$$\end{document}NORMALIZE-ROWS also defines a mapping \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Rows} : \textbf{A} \mapsto \textbf{B}, {{\boldsymbol{y}}}$$\end{document}NORMALIZE-ROWS:A↦B,y, with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A} \in \textbf{R}_{+}^{r \times c}$$\end{document}A∈R+r×c, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{B} \in \textbf{R}_{\textrm{row}}^{r \times c}$$\end{document}B∈Rrowr×c, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{y} \in \textbf{R}_{++}^r$$\end{document}y∈R++r. If each row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A has at least one positive element, then this mapping is one-to-one, and therefore \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Rows}$$\end{document}NORMALIZE-ROWS defines a change of variables from non-negative matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A to row-normalized matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{B}$$\end{document}B and positive vectors \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{y}}}$$\end{document}y. Similarly, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Normalize-\!Cols} : \textbf{A} \mapsto \textbf{B}, {{\boldsymbol{y}}}$$\end{document}NORMALIZE-COLS:A↦B,y defines a change of variables from non-negative matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A to column-normalized matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{B}$$\end{document}B and positive vectors \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{y}}}$$\end{document}y (provided that each column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A}$$\end{document}A has at least one positive element). These together imply that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {MTM-\!to-\!PNMF}$$\end{document}MTM-TO-PNMF defines a change of variables from non-negative matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W to positive vectors \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{s}}}, {{\boldsymbol{u}}}$$\end{document}s,u, row-normalized matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L, and column-normalized matrices \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}$$\end{document}F. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}$$\end{document}F and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L satisfy the sum-to-one constraints (5). The inverse mapping, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {MTM-\!to-\!PNMF}~{:}{=}~ \textsc {PNMF-\!to-\!MTM}^{-1} : \textbf{L}, \textbf{F}, {{\boldsymbol{s}}}, {{\boldsymbol{u}}} \mapsto \textbf{H}, \textbf{W}$$\end{document}MTM-TO-PNMF:=PNMF-TO-MTM-1:L,F,s,u↦H,W, is \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W} \leftarrow \textbf{F}\textbf{U}$$\end{document}W←FU, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H} \leftarrow \textbf{S} \textbf{L}\textbf{U}^{-1}$$\end{document}H←SLU-1, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{U}~{:}{=}~ \textrm{diag}({{\boldsymbol{u}}})$$\end{document}U:=diag(u), \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{S}~{:}{=}~ \textrm{diag}({{\boldsymbol{s}}})$$\end{document}S:=diag(s). Lemma 1 (Equivalence of Poisson NMF and multinomial topic model likelihoods) Denote the Poisson NMF likelihood by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\textrm{PNMF}}({\textbf{X}} \mid \textbf{H}, \textbf{W})$$\end{document}pPNMF(X∣H,W) and denote the multinomial topic model likelihood by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\textrm{MTM}}({\textbf{X}} \mid \textbf{L}, \textbf{F})$$\end{document}pMTM(X∣L,F). Assume \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H} \in \textbf{R}_{+}^{n \times K}$$\end{document}H∈R+n×K and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W} \in \textbf{R}_{+}^{m \times K}$$\end{document}W∈R+m×K, define \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t_i~{:}{=}~ \sum _{j=1}^m x_{ij}$$\end{document}ti:=∑j=1mxij, and let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}, \textbf{F}, {{\boldsymbol{s}}}, {{\boldsymbol{u}}}$$\end{document}L,F,s,u be the result of applying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}$$\end{document}PNMF-TO-MTM to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W. Then we have that8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} p_{\textrm{PNMF}}({\textbf{X}} \mid \textbf{H}, \textbf{W}) = p_{\textrm{MTM}}({\textbf{X}} \mid \textbf{L}, \textbf{F}) \prod _{i=1}^n \textrm{Pois}(t_i; s_i), \end{aligned}$$\end{document}pPNMF(X∣H,W)=pMTM(X∣L,F)∏i=1nPois(ti;si),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{Pois}(x; \lambda )$$\end{document}Pois(x;λ) denotes the probability mass function of the Poisson distribution at x with rate \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document}λ. Proof The result is obtained by applying the following identity relating the multinomial and Poisson distributions (Fisher 1922; Good 1986):9\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \prod _{j=1}^m \textrm{Pois}(x_j; \lambda _j) = \textrm{Multin}({\boldsymbol{x}}; t, \lambda _1/s, \ldots , \lambda _m/s) \textrm{Pois}(t; s), \end{aligned}$$\end{document}∏j=1mPois(xj;λj)=Multin(x;t,λ1/s,…,λm/s)Pois(t;s),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\boldsymbol{x}} = (x_1, \dots , x_m)$$\end{document}x=(x1,⋯,xm), \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda _1, \ldots , \lambda _m \in \textbf{R}_{+}$$\end{document}λ1,…,λm∈R+, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s~{:}{=}~ \sum _{j=1}^m \lambda _j$$\end{document}s:=∑j=1mλj, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t~{:}{=}~ \sum _{j=1}^m x_j$$\end{document}t:=∑j=1mxj, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{Multin}({{\boldsymbol{x}}}; n, \pi _1, \ldots , \pi _m)$$\end{document}Multin(x;n,π1,…,πm) denotes the probability mass function of the multinomial distribution at \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{x}}} = (x_1, \ldots , x_m)$$\end{document}x=(x1,…,xm) with sample size n and probabilities \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _1, \ldots , \pi _m$$\end{document}π1,…,πm. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\square $$\end{document}□ Now we use this lemma to justify solving the Poisson NMF optimization problem in order to achieve maximum-likelihood estimation in the multinomial topic model. First, consider an augmented form of the multinomial topic model optimization problem:10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \phi _{\textrm{aug}}(\textbf{X}; \textbf{L}, \textbf{F}, {{\boldsymbol{s}}}) \\ \text{ subject } \text{ to } & \textbf{L} {\boldsymbol{1}}_K = {\boldsymbol{1}}_n \\ & \textbf{F}^T {\boldsymbol{1}}_m = {\boldsymbol{1}}_K \\ & \textbf{L} \ge {\boldsymbol{0}}, \textbf{F} \ge {\boldsymbol{0}}, {{\boldsymbol{s}}} \ge {\boldsymbol{0}}, \end{array} \end{aligned}$$\end{document}minimizeϕaug(X;L,F,s)subjecttoL1K=1nFT1m=1KL≥0,F≥0,s≥0,in which the augmented objective is11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \phi _{\textrm{aug}}(\textbf{X}; \textbf{L}, \textbf{F}, {{\boldsymbol{s}}})~{:}{=}~ \phi (\textbf{X}; \textbf{L}, \textbf{F}) + \psi (\textbf{X}; {{\boldsymbol{s}}}) \end{aligned}$$\end{document}ϕaug(X;L,F,s):=ϕ(X;L,F)+ψ(X;s)12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \psi (\textbf{X}; {{\boldsymbol{s}}})~{:}{=}~ \sum _{i=1}^n s_i - \sum _{i=1}^n \sum _{j=1}^m x_{ij} \log s_i. \end{aligned}$$\end{document}ψ(X;s):=∑i=1nsi-∑i=1n∑j=1mxijlogsi.Notice that solutions to (10) are also solutions to (7) because the objective and constraints for the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}$$\end{document}F have not changed. The Poisson NMF objective \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell (\textbf{X}; \textbf{H}, \textbf{W})$$\end{document}ℓ(X;H,W) is equal to the Poisson log-likelihood, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\log p_{\textrm{PNMF}}({\textbf{X}} \mid \textbf{H}, \textbf{W})$$\end{document}logpPNMF(X∣H,W) (ignoring constant terms), and the multinomial topic model augmented objective \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _{\textrm{aug}}(\textbf{X}; \textbf{L}, \textbf{F}, \textbf{s})$$\end{document}ϕaug(X;L,F,s) is equal to the logarithm of the right-hand side of (8) (again, ignoring constant terms). This means that any optimization algorithm that improves the Poisson NMF objective \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell (\textbf{X}; \textbf{H}, \textbf{W})$$\end{document}ℓ(X;H,W) will also improve the augmented objective \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi _{\textrm{aug}}(\textbf{X}; \textbf{L}, \textbf{F}, \textbf{s})$$\end{document}ϕaug(X;L,F,s) so long as \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}$$\end{document}PNMF-TO-MTM is used to to recover \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}, \textbf{F}, {{\boldsymbol{s}}}$$\end{document}L,F,s from \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W. We formalize the relationship between the two optimization problems in the following corollary. Corollary 1 (Relationship between MLEs for Poisson NMF and multinomial topic model) Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}} \in \textbf{R}_{+}^{n \times K}, \hat{\textbf{W}} \in \textbf{R}_{+}^{m \times K}$$\end{document}H^∈R+n×K,W^∈R+m×K denote MLEs for the Poisson NMF model,313\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \hat{\textbf{H}}, \hat{\textbf{W}} \in \underset{\textbf{H} \in \textbf{R}_{+}^{n \times K}, \textbf{W} \in \textbf{R}_{+}^{m \times K}}{\textrm{argmax}} p_{\textrm{PNMF}}(\textbf{X}\mid \textbf{H}, \textbf{W}). \end{aligned}$$\end{document}H^,W^∈argmaxH∈R+n×K,W∈R+m×KpPNMF(X∣H,W).Equivalently, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}}, \hat{\textbf{W}}$$\end{document}H^,W^ can be defined as a solution to (2). If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}}, \hat{\textbf{F}}$$\end{document}L^,F^ are obtained by applying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}$$\end{document}PNMF-TO-MTM to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}}, \hat{\textbf{W}}$$\end{document}H^,W^, then these are also MLEs for the multinomial topic model,14\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \hat{\textbf{L}}, \hat{\textbf{F}} \in \underset{\textbf{L} \,\in \, \textbf{R}_{\textrm{row}}^{n \times K}, \, \textbf{F} \,\in \, \textbf{R}_{\textrm{col}}^{m \times K}}{\textrm{argmax}} \; p_{\textrm{MTM}}(\textbf{X}\mid \textbf{L}, \textbf{F}). \end{aligned}$$\end{document}L^,F^∈argmaxL∈Rrown×K,F∈Rcolm×KpMTM(X∣L,F).Equivalently, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}}, \hat{\textbf{F}}$$\end{document}L^,F^ are a solution to (7). Conversely, let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}} \in \textbf{R}_{\textrm{row}}^{n \times K}, \hat{\textbf{F}} \in \textbf{R}_{\textrm{col}}^{m \times K}$$\end{document}L^∈Rrown×K,F^∈Rcolm×K denote multinomial topic model MLEs, set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{{\boldsymbol{s}}} = {{\boldsymbol{t}}}~{:}{=}~ (t_1, \ldots , t_n)$$\end{document}s^=t:=(t1,…,tn), and choose any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{{\boldsymbol{u}}} \in \textbf{R}_{++}^K$$\end{document}u^∈R++K. If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}}, \hat{\textbf{W}}$$\end{document}H^,W^ are obtained by applying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {MTM-\!to-\!PNMF}$$\end{document}MTM-TO-PNMF to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}}, \hat{\textbf{F}}, \hat{{\boldsymbol{s}}}, \hat{{\boldsymbol{u}}}$$\end{document}L^,F^,s^,u^, these are also Poisson NMF MLEs (13). Proof We prove this result using “equivalent optimization problems” (Boyd and Vandenberghe 2004). Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}$$\end{document}PNMF-TO-MTM defines a change of variables, we can apply the change of variables to (10) to obtain an equivalent optimization problem with optimization variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W:15\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \phi _{\textrm{aug}}(\textbf{X}; \textsc {PNMF-\!to-\!MTM}(\textbf{H}, \textbf{W})) \\ \text{ subject } \text{ to } & \textbf{H} \ge {{\boldsymbol{0}}}, \textbf{W} \ge {{\boldsymbol{0}}}, \end{array} \end{aligned}$$\end{document}minimizeϕaug(X;PNMF-TO-MTM(H,W))subjecttoH≥0,W≥0,in which the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{u}}}$$\end{document}u returned by PNMF-to-MTM is ignored. From Lemma 1, we can rewrite (15) as16\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \ell (\textbf{X}; \textbf{H}, \textbf{W}) + \text{ const } \\ \text{ subject } \text{ to } & \textbf{H} \ge {{\boldsymbol{0}}}, \textbf{W} \ge {{\boldsymbol{0}}}, \end{array} \end{aligned}$$\end{document}minimizeℓ(X;H,W)+constsubjecttoH≥0,W≥0,which is exactly the Poisson NMF optimization problem (ignoring terms that do not depend on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H or \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W). Therefore, the augmented optimization problem (10) and the Poisson NMF optimization problem (2) are related to each other by the change of variables \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}(\textbf{H}, \textbf{W}) = (\textbf{L}, \textbf{F}, {{\boldsymbol{s}}}, {{\boldsymbol{u}}})$$\end{document}PNMF-TO-MTM(H,W)=(L,F,s,u). Since solutions to the augmented optimization problem (10) are also solutions to the original problem (7), it follows that Poisson NMF MLEs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}}, \hat{\textbf{W}}$$\end{document}H^,W^ recover multinomial topic model MLEs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}}, \hat{\textbf{F}}$$\end{document}L^,F^. The reverse—that multinomial topic model MLEs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{L}}, \hat{\textbf{F}}$$\end{document}L^,F^ recover Poisson NMF MLEs \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{H}}, \hat{\textbf{W}}$$\end{document}H^,W^—requires the additional step of solving \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{\textbf{s}}~{:}{=}~ \textrm{argmin}_{{{\boldsymbol{s}}} \,\in \, \textbf{R}_{++}^n} \psi ({{\boldsymbol{s}}}) = \textrm{argmax}_{{{\boldsymbol{s}}} \,\in \, \textbf{R}_{++}^n} \prod _{i=1}^n \textrm{Pois}(t_i; s_i)$$\end{document}s^:=argmins∈R++nψ(s)=argmaxs∈R++n∏i=1nPois(ti;si), which has unique solution \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hat{{\boldsymbol{s}}} = {{\boldsymbol{t}}}$$\end{document}s^=t provided that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t_1, \ldots , t_n > 0$$\end{document}t1,…,tn>0. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\square $$\end{document}□ Remark 1 Since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W are not uniquely identifiable—consider that multiplying the kth column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_k \ne 0$$\end{document}ak≠0 and dividing the kth column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W by \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_k$$\end{document}ak does not change \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H} \textbf{W}^T$$\end{document}HWT—one way to avoid this non-identifiability is to impose constraints or penalty terms to the objective. However, introducing constraints or penalties on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W (or \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}, \textbf{F}$$\end{document}L,F) may break the above equivalence. We note one form of penalized objective that preserves the equivalence:17\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \phi ^{\star }(\textbf{X}; \textbf{L}, \textbf{F})~{:}{=}~ \phi (\textbf{X}; \textbf{L}, \textbf{F}) + \rho ^{\textrm{MTM}}(\textbf{F}), \end{aligned}$$\end{document}ϕ⋆(X;L,F):=ϕ(X;L,F)+ρMTM(F),where18\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \rho ^{\textrm{MTM}}(\textbf{F})~{:}{=}~ -\sum _{j=1}^m \sum _{k=1}^K (a_{jk} - 1) \log f_{jk}, \end{aligned}$$\end{document}ρMTM(F):=-∑j=1m∑k=1K(ajk-1)logfjk,and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{jk} > 1$$\end{document}ajk>1, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j = 1, \ldots , m$$\end{document}j=1,…,m, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 1, \ldots , K$$\end{document}k=1,…,K. The equivalent penalized objective for Poisson NMF is19\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \ell ^{\star }(\textbf{X}; \textbf{H}, \textbf{W})~{:}{=}~ \ell (\textbf{X}; \textbf{H}, \textbf{W}) + \rho ^{\textrm{PNMF}}(\textbf{W}), \end{aligned}$$\end{document}ℓ⋆(X;H,W):=ℓ(X;H,W)+ρPNMF(W),where20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \rho ^{\textrm{PNMF}}(\textbf{W})~{:}{=}~\;&- \sum _{j=1}^m \sum _{k=1}^K (a_{jk} - 1) \log w_{jk} \nonumber \\&+ \sum _{j=1}^m \sum _{k=1}^K b_k w_{jk}, \end{aligned}$$\end{document}ρPNMF(W):=-∑j=1m∑k=1K(ajk-1)logwjk+∑j=1m∑k=1Kbkwjk,and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_k > 0$$\end{document}bk>0, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 1, \ldots , K$$\end{document}k=1,…,K. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{jk}, b_k$$\end{document}ajk,bk control the shape and strength of these penalties. (Setting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a_{jk} = 1, b_k = 0$$\end{document}ajk=1,bk=0 recovers the unpenalized objectives.) Minimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\phi ^{\star }(\textbf{X}; \textbf{L}, \textbf{F})$$\end{document}ϕ⋆(X;L,F) corresponds to MAP estimation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}, \textbf{F}$$\end{document}L,F with Dirichlet priors on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}$$\end{document}F and uniform priors on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L (Sontag et al. 2011), and minimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell ^{\star }(\textbf{X}; \textbf{H}, \textbf{W})$$\end{document}ℓ⋆(X;H,W) corresponds to MAP estimation of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}, \textbf{H}$$\end{document}W,H with gamma priors on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W and uniform priors on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H (Canny 2004; Cemgil 2009; Ma et al. 2011). The equivalence of MAP estimation with these specific priors is a slight generalization of Corollary 1 (see Appendix A). Lemma 1 and Corollary 1 are more general than previous results (Buntine and Jakulin 2006; Ding et al. 2008; Gaussier and Goutte 2005; Gillis 2021) because they apply to any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}, \textbf{W}$$\end{document}H,W and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}, \textbf{F}$$\end{document}L,F from Definition 1, not only a fixed point of the likelihood or objective. See Buntine (2002); Faleiros et al. (2016); Zhou et al. (2012) for other related results. In short, Lemma 1 tells us that Poisson NMF and the multinomial topic model are Poisson and multinomial formulations of the same matrix factorization method. In particular, their shared ability to recover a decomposition into “parts” or “topics” is suggested by these formal connections. Although Poisson NMF and the multinomial topic model achieve similar ends, the two methods still possess different advantages: Poisson NMF has an advantage in computation because it avoids the sum-to-one constraints, whereas the multinomial topic model has the advantage in interpretation because the parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$f_{jk}, l_{ik}$$\end{document}fjk,lik can be compared across topics k (the Poisson NMF parameters \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$h_{ik}, w_{jk}$$\end{document}hik,wjk cannot due to the undetermined column-scaling \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{u}}}$$\end{document}u). Therefore, by switching between the two models, we can have the advantages of both. Poisson NMF algorithms Corollary 1 implies that any algorithm for maximum-likelihood estimation in Poisson NMF is also an algorithm for maximum-likelihood estimation in the multinomial topic model. (This also means that the NP-hardness (Arora et al. 2012; Vavasis 2010) of the two problems is related.) Fitting the Poisson NMF model involves solving (2), which we restate here in a slightly different way:21\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{ll} \text{ minimize } & \displaystyle \ell (\textbf{X}; \textbf{H},\textbf{W}) = \sum _{i=1}^n \sum _{j=1}^m {{\boldsymbol{h}}}_i^T {{\boldsymbol{w}}}_j - x_{ij} \log ({{\boldsymbol{h}}}_i^T {{\boldsymbol{w}}}_j) \\ \text{ subject } \text{ to } & \textbf{H} \ge \textbf{0}, \textbf{W} \ge \textbf{0}, \end{array} \end{aligned}$$\end{document}minimizeℓ(X;H,W)=∑i=1n∑j=1mhiTwj-xijlog(hiTwj)subjecttoH≥0,W≥0,Here, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{h}}}_i$$\end{document}hi and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{w}}}_j$$\end{document}wj denote column vectors containing, respectively, the ith row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H and the jth row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W, and we assume \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K \ge 2$$\end{document}K≥2. To facilitate comparisons of different algorithms for solving (21), in the next section we introduce an “Alternating Poisson Regression” framework for solving (21), then we describe the algorithms we have implemented, drawing on recent work and our own experimentation. See also Hien and Gillis (2021) for a detailed comparison of Poisson NMF algorithms. Alternating Poisson Regression for Poisson NMF Alternating Poisson Regression arises from solving (21) by switching between optimizing over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W fixed, and optimizing over \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H fixed. This is an example of a block-coordinate descent algorithm (Wright (2015); Bertsekas (1999)) where the two “blocks” are \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W. It is analogous to “alternating least squares” for matrix factorization with Gaussian errors. We point out two simple but important facts. First, by symmetry of (21), optimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H given \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W has the same form as optimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W given \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H. Second, because of the separability of the sum in (21), optimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W given \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H splits into m independent K-dimensional subproblems of the following form:22\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{array}{l@{\;}l} \text{ minimize } & \ell _j({{\boldsymbol{w}}}_j)~{:}{=}~ \sum _{i=1}^n {{\boldsymbol{h}}}_i^T{{\boldsymbol{w}}}_j - x_{ij} \log ({{\boldsymbol{h}}}_i^T{{\boldsymbol{w}}}_j) \\ \text{ subject } \mathrm{ to } & {{\boldsymbol{w}}}_j \ge {{\boldsymbol{0}}}, \end{array} \end{aligned}$$\end{document}minimizeℓj(wj):=∑i=1nhiTwj-xijlog(hiTwj)subjecttowj≥0,for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$j = 1, \dots , m$$\end{document}j=1,⋯,m. (And similarly for optimizing \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H given \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W.) Because the m subproblems (22) are independent, their solutions can be pursued in parallel. While both of these observations are simple, neither of them hold for the multinomial topic model due to the sum-to-one constraints. Subproblem (22) is itself a well-studied maximum-likelihood estimation problem (McLachlan and Krishnan (2008); Lange and Carson (1984); Lucy (1974); Molina et al. (2001); Richardson (1972); Shepp and Vardi (1982); Vardi et al. (1985)), and it is equivalent to computing an MLE of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{b}}}~{:}{=}~ (b_1, \ldots , b_K)^T \ge {{\boldsymbol{0}}}$$\end{document}b:=(b1,…,bK)T≥0 in an additive Poisson regression model:23\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \begin{aligned} y_i&\sim \textrm{Pois}(\mu _i) \\ \mu _i&= \textstyle \sum _{k=1}^K a_{ik} b_k, \end{aligned} \end{aligned}$$\end{document}yi∼Pois(μi)μi=∑k=1Kaikbk,in which \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{y}}} = (y_1, \ldots , y_n)^T \in \textbf{R}_{+}^n$$\end{document}y=(y1,…,yn)T∈R+n and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{A} \in \textbf{R}_{+}^{n \times K}$$\end{document}A∈R+n×K. Consider a function that returns an MLE of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{b}}}$$\end{document}b for (23),24\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \textsc {Fit-\!Pois-\!Reg}(\textbf{A}, {{\boldsymbol{y}}})~{:}{=}~ \underset{{{\boldsymbol{b}}} \, \in \, \textbf{R}_{+}^K}{\textrm{argmax}} \; p_{\textrm{PR}}({{\boldsymbol{y}}} \mid \textbf{A}, {{\boldsymbol{b}}}), \end{aligned}$$\end{document}FIT-POIS-REG(A,y):=argmaxb∈R+KpPR(y∣A,b),where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_{\textrm{PR}}({{\boldsymbol{y}}} \mid \textbf{A}, {{\boldsymbol{b}}})$$\end{document}pPR(y∣A,b) denotes the likelihood under the Poisson regression model (23). Any algorithm that solves (24) be can applied iteratively to solve the Poisson NMF problem (21). This idea, which we call “alternating Poisson regression for Poisson NMF”, is formalized in Algorithm 1. Algorithm 1Alternating Poisson Regression for Poisson NMF. Here, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{x}}}_i$$\end{document}xi denotes a row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textbf{X}}$$\end{document}X and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{x}}}_j$$\end{document}xj denotes a column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{X}$$\end{document}X. Alternating Poisson Regression for Poisson NMF. Here, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{x}}}_i$$\end{document}xi denotes a row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\textbf{X}}$$\end{document}X and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\boldsymbol{x}}}_j$$\end{document}xj denotes a column of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{X}$$\end{document}X. Specific algorithms We now consider different approaches to solving \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Fit-\!Pois-\!Reg}(\textbf{A}, {{\boldsymbol{y}}})$$\end{document}FIT-POIS-REG(A,y), which, when inserted into Algorithm 1, produce different Poisson NMF algorithms. These algorithms are closely connected to existing algorithms for Poisson NMF and/or the multinomial topic model (Table 1). Expectation maximization There is a long history of solving the Poisson regression problem (24) by EM (Dempster et al. (1977); De Pierro (1993); McLachlan and Krishnan (2008); Krishnan (1995); Lange and Carson (1984); Lucy (1974); Meng and Van Dyk (1997); Molina et al. (2001); Richardson (1972); Shepp and Vardi (1982); Vardi et al. (1985); Vardi and Lee (1993)). The EM updates for this problem consist of iterating the following updates:25\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} \bar{z}_{ik}&= y_i a_{ik} b_k / \mu _i \end{aligned}$$\end{document}z¯ik=yiaikbk/μi26\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} b_k&= \frac{\sum _{i=1}^n \bar{z}_{ik}}{\sum _{i=1}^n a_{ik}}, \end{aligned}$$\end{document}bk=∑i=1nz¯ik∑i=1naik,where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bar{z}_{ik}$$\end{document}z¯ik represents a posterior expectation in an equivalent augmented model (see Appendix A). This EM algorithm is closely connected to the multiplicative update rules for Poisson NMF (Lee and Seung 2001): combining the E step (25) and M step (26) with the substitutions used in Algorithm 1 yields27\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} h_{ik}^{\textrm{new}}&\leftarrow h_{ik} \times \frac{\sum _{j=1}^m x_{ij} w_{jk} / \lambda _{ij}}{\sum _{j=1}^m w_{jk}} \end{aligned}$$\end{document}hiknew←hik×∑j=1mxijwjk/λij∑j=1mwjk28\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} w_{jk}^{\textrm{new}}&\leftarrow w_{jk} \times \frac{\sum _{i=1}^n x_{ij} h_{ik} / \lambda _{ij}}{\sum _{i=1}^n h_{ik}}, \end{aligned}$$\end{document}wjknew←wjk×∑i=1nxijhik/λij∑i=1nhik,which are precisely the multiplicative updates for Poisson NMF. See Appendix A for the derivation. Additionally, applying \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {PNMF-\!to-\!MTM}$$\end{document}PNMF-TO-MTM to the multiplicative updates (27, 28) recovers the EM updates for the multinomial topic model (Asuncion et al. (2009); Buntine (2002); Gaussier and Goutte (2005); Hofmann (2001)). See Appendix A for the derivation. Therefore, when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Fit-\!Pois-\!Reg}(\textbf{A}, {{\boldsymbol{y}}})$$\end{document}FIT-POIS-REG(A,y) is solved using EM, Algorithm 1 can be viewed as implementing “stepwise” variants of the multiplicative updates for Poisson NMF, or EM for the multinomial topic model (Table 1). By “stepwise”, we mean that the update order suggested by Algorithm 1 is to iterate the E and M steps for the first row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H, then for the second row of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{H}$$\end{document}H, and so on, followed by updates to rows of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{W}$$\end{document}W. This is in contrast to a typical EM algorithm in which all E-step updates are performed first, then all M-step updates are performed.Table 1Relationship between maximum-likelihood estimation algorithms for the additive Poisson regression model, Poisson NMF, and the multinomial topic model. Abbreviations used: EM = expectation maximization (Shepp and Vardi 1982; Hofmann 1999), MU = multiplicative updates (Lee and Seung 1999, 2001), CD = co-ordinate descent (Bouman and Sauer 1996), CCD = cyclic co-ordinate descent (Hsieh and Dhillon 2011), SCD = sequential co-ordinate descent (Lin and Boutros 2020).Additive Poisson regressionPoisson NMFtopic modelEMMUEMCDCCD, SCDnone Table 1Relationship between maximum-likelihood estimation algorithms for the additive Poisson regression model, Poisson NMF, and the multinomial topic model. Abbreviations used: EM = expectation maximization (Shepp and Vardi 1982; Hofmann 1999), MU = multiplicative updates (Lee and Seung 1999, 2001), CD = co-ordinate descent (Bouman and Sauer 1996), CCD = cyclic co-ordinate descent (Hsieh and Dhillon 2011), SCD = sequential co-ordinate descent (Lin and Boutros 2020).Additive Poisson regressionPoisson NMFtopic modelEMMUEMCDCCD, SCDnone Relationship between maximum-likelihood estimation algorithms for the additive Poisson regression model, Poisson NMF, and the multinomial topic model. Abbreviations used: EM = expectation maximization (Shepp and Vardi 1982; Hofmann 1999), MU = multiplicative updates (Lee and Seung 1999, 2001), CD = co-ordinate descent (Bouman and Sauer 1996), CCD = cyclic co-ordinate descent (Hsieh and Dhillon 2011), SCD = sequential co-ordinate descent (Lin and Boutros 2020). Co-ordinate descent Co-ordinate descent is an alternative to EM that iteratively optimizes a single co-ordinate while the remaining co-ordinates are fixed (see also (Bouman and Sauer 1996)). For the Poisson regression problem, each 1-d optimization is straightforward to implement via Newton’s method,29\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} b_k^{\textrm{new}} \leftarrow \max \{0, b_k - \alpha _k g_k/q_k \}, \end{aligned}$$\end{document}bknew←max{0,bk-αkgk/qk},where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k \ge 0$$\end{document}αk≥0 is a step size that can be determined by a line search or some other method, and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g_k$$\end{document}gk and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$q_k$$\end{document}qk are the partial derivatives with respect to the negative log-likelihood \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{\textrm{PR}}({{\boldsymbol{b}}})~{:}{=}~ -\log p_{\textrm{PR}}({{\boldsymbol{y}}} \mid \textbf{A}, {{\boldsymbol{b}}})$$\end{document}ℓPR(b):=-logpPR(y∣A,b),30\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} g_k&~{:}{=}~~\frac{\partial \ell _{\textrm{PR}}}{\partial b_k} = \sum _{i=1}^n a_{ik} \left( 1 - \frac{y_i}{\mu _i}\right) \end{aligned}$$\end{document}gk:=∂ℓPR∂bk=∑i=1naik1-yiμi31\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{aligned} q_k&~{:}{=}~~\frac{\partial ^2 \ell _{\textrm{PR}}}{\partial b_k^2} = \sum _{i=1}^n \frac{y_i a_{ik}^2}{\mu _i^2}. \end{aligned}$$\end{document}qk:=∂2ℓPR∂bk2=∑i=1nyiaik2μi2.Several Poisson NMF algorithms, including cyclic co-ordinate descent (CCD) (Hsieh and Dhillon 2011), sequential co-ordinate descent (SCD) (Lin and Boutros 2020) and scalar Newton (SN) (Hien and Gillis 2021), can be viewed as implementing variants of this CD approach. That is, these approaches are essentially Algorithm 1 in which \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsc {Fit-\!Pois-\!Reg}(\textbf{A}, {{\boldsymbol{y}}})$$\end{document}FIT-POIS-REG(A,y) is solved by CD. The CCD and SCD methods appear to be independent developments of the same or very similar algorithm; they both take a full (feasible) Newton step, setting \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k = 1$$\end{document}αk=1 when \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b_k - \alpha _k g_k/q_k > 0$$\end{document}bk-αkgk/qk>0. By foregoing a line search to determine \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _k$$\end{document}αk, the update is not guaranteed to decrease the objective \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell _{\textrm{PR}}({{\boldsymbol{b}}})$$\end{document}ℓPR(b). The SN method was developed to remedy this issue, with a step size scheme that always produces a decrease while avoiding the expense of a line search. However, Hien and Gillis (2021) compared SN with CCD and found that CCD usually performed best in real data sets despite not having a line search. Although the CD approach is straightforward for Poisson NMF, it is not straightforward for the multinomial topic model due to the sum-to-one constraints. Numerical experiments To summarize, we have described two variants of Algorithm 1 for Poisson NMF (Table 1): the first fits an “additive Poisson regression” model using EM, and is essentially the same as existing EM algorithms for Poisson NMF and the multinomial topic model (including the Poisson NMF multiplicative updates); the second uses co-ordinate descent (CD) to fit the additive Poisson regression model, and has no equivalent among existing algorithms for the multinomial topic model. In the remainder, we refer to these two variants of Algorithm 1 as “EM” and “CD”.Fig. 1Results of fitting multinomial topic models to the MCF-7 data set (Sanford et al. 2020) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 3$$\end{document}K=3. Plots A–C show estimates of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$41 \times 3$$\end{document}41×3 matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L: the initial estimates (obtained by running 4 EM updates); the MLE (obtained by running many CD updates, starting from the initial estimates); and the estimates obtained by running 200 EM updates starting from the initial estimates. Each estimate of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L is visualized using a “Structure plot” (Rosenberg 2002), which is a stacked bar chart in which the bar heights are given by the elements of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L. Plots D, E show the improvement in the multinomial topic model fits over time. Multinomial topic model log-likelihoods are shown relative to the log-likelihood of the multinomial topic model at the MLE (B); points highest on the y-axis indicate the worst log-likelihoods. Results of fitting multinomial topic models to the MCF-7 data set (Sanford et al. 2020) with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 3$$\end{document}K=3. Plots A–C show estimates of the \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$41 \times 3$$\end{document}41×3 matrix \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L: the initial estimates (obtained by running 4 EM updates); the MLE (obtained by running many CD updates, starting from the initial estimates); and the estimates obtained by running 200 EM updates starting from the initial estimates. Each estimate of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L is visualized using a “Structure plot” (Rosenberg 2002), which is a stacked bar chart in which the bar heights are given by the elements of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L. Plots D, E show the improvement in the multinomial topic model fits over time. Multinomial topic model log-likelihoods are shown relative to the log-likelihood of the multinomial topic model at the MLE (B); points highest on the y-axis indicate the worst log-likelihoods. We begin with an in-depth example on a real data set to illustrate the differences between the EM and CD algorithms. The data for this example are RNA-sequencing read counts for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n = 41$$\end{document}n=41 samples and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m = \text{1 }6, 773$$\end{document}m=16,773 genes from Sanford et al. (2020). This data set provides a ground truth of sorts for fitting the topic model: the data are gene expression measurements taken after human MCF-7 cells were exposed to either ethanol (EtOH), retinoic acid (RA), TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β, or the combination of RA and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β. Therefore, the topic model with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 3$$\end{document}K=3 topics should reflect the three exposures—EtOH, RA and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β—and samples in the combined exposure should be modeled as a combination of the RA and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β topics. Indeed, the MLE we obtained by running the Poisson NMF algorithm for a long time (with CD updates) largely produced the expected result: the samples in the ethanol condition were mostly represented by a single topic (the “ethanol topic”); the samples in the combination treatment were an even combination of the RA and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β topics; and the samples exposed to either RA and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β were represented as combinations of the ethanol and RA topics or the ethanol and TGF-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta $$\end{document}β topics (Fig. 1B). The steps taken to prepare these data for topic modeling are detailed in Appendix C. The code implementing this experiment is provided in a Zenodo repository (Carbonetto et al. 2024), and is available online at https://github.com/stephenslab/fastTopics-experiments/. To compare the performance of EM and CD on this data set, we first initialized the Poisson NMF parameters at random, then we ran 4 EM updates to slightly improve upon this random initialization. The resulting initial estimate of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L is shown in Fig. 1A. Next, starting from this initial estimate, we ran 200 EM updates or 200 CD updates. (“Update” here means one iteration of the outer loop of Algorithm 1.) The CD updates produced estimates very close to the MLE; the distance to the MLE in log-likelihood units was just 0.079 (Fig. 1D). By contrast, the EM estimates remained very far away from the MLE after 200 iterations, at a distance of over 150,000 log-likelihood units (Fig. 1D). The EM estimates after 200 iterations (Fig. 1C) were also qualitatively very different from the MLE. The EM estimates are arguably less interpretable because they do not correspond as well to the exposures. To rule out the possibility the EM was unlucky and had settled into a different local maximum of the likelihood, we ran many more EM updates. Eventually, EM recovered the same MLE (Fig. 1E). Therefore, the very slow progress of EM could not be explained by having converged to a less optimal stationary point. One could conclude from this comparison that good estimates could be obtained simply by running the EM updates for a long time. However, this is often impractical for larger data sets. Another algorithmic innovation we present here is the use of the extrapolation method (Ang and Gillis 2019) to accelerate convergence of the Poisson NMF algorithm. The idea behind the extrapolation method, which builds on the method of parallel tangents (Luenberger and Ye 2015), is to avoid the “zigzagging” behaviour of the block-coordinate updates by iteratively adapting the step size according to the performance of the extrapolated updates compared to the non-extrapolated updates. The additional operations needed to implement the extrapolated updates impose minimal overhead. The extrapolation method was originally applied to Frobenius-norm NMF, and to our knowledge it has not been used to accelerate algorithms for Poisson NMF, or for fitting topic models. (More details on the extrapolation method and its implementation for Poisson NMF are given in Appendix B.) To illustrate the benefits of extrapolation, we activated the extrapolation method at iteration 50 of the CD algorithm. Doing so allowed the CD updates to recover the MLE much more quickly than the non-extrapolated CD updates (Fig. 1D). Further, when we applied the extrapolated CD updates to the EM estimates, they quickly “rescued” the poor EM estimates (Fig. 1D), further suggesting that the slow progress of EM was not due to some fundamental difficulty of the objective, but rather due to properties of the EM updates. In summary, the results from this example suggest the potential for NMF methods—in particular, Algorithm 1 with CD updates plus extrapolation—to improve maximum-likelihood estimation for the multinomial topic model. To assess this more systematically, we performed comparisons of the EM and CD variants in a variety of data sets (Table 2): two text data sets (Globerson et al. 2007; Rennie 2007) that have been used to evaluate topic modeling methods (e.g., Asuncion et al. 2009; Wallach 2006); and two single-cell RNA sequencing (scRNA-seq) data sets (Montoro et al. 2018; Zheng et al. 2017). Appendix C gives additional details on these data sets and the experiment setup. All the algorithms compared in these experiments were implemented in the fastTopics R package. These R implementations include the enhancements described in Appendix B intended to make the algorithms more efficient and numerically stable. The code implementing these experiments is provided in a Zenodo repository (Carbonetto et al. 2024), and is available online at https://github.com/stephenslab/fastTopics-experiments/.Table 2Data sets used in the experiments.namerowscolumnsnonzerosNeurIPS2,48314,0363.7%newsgroups18,77455,9110.2%epithelial airway7,19318,3889.3%68k PBMC68,57920,3872.7% Table 2Data sets used in the experiments.namerowscolumnsnonzerosNeurIPS2,48314,0363.7%newsgroups18,77455,9110.2%epithelial airway7,19318,3889.3%68k PBMC68,57920,3872.7% Data sets used in the experiments. To reduce the possibility that multiple optimizations converge to different local maxima of the likelihood, which could complicate the comparisons, we first ran 1,000 EM updates—that is, 1,000 iterations of the outer loop of Algorithm 1—then we examined the performance of the algorithms after this initialization phase. Therefore, in our comparisons we assessed the extent to which the different algorithms improved upon this initialization. Another issue was that it was not always practical to run the optimization algorithms long enough to obtain an accurate MLE. Therefore, instead of comparing the estimates to the MLE, like we did in the example above, we used as a reference point the best estimate (in log-likelihood) that was obtained.Fig. 2Selected results on fitting topic models using Poisson NMF algorithms. In A1–F1, multinomial topic model log-likelihoods are given relative to the best log-likelihood obtained among the four algorithms compared (EM and CD, with and without extrapolation). Log-likelihood differences less than 0.01 are shown as 0.01, and circles are drawn at intervals of 100 iterations. The 1,000 EM iterations performed during the initialization phase are not shown. Plots A2–F2 compare the final estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from each of A1–F1. See also Figures 5–12 in the Appendix for additional results obtained with different settings of K.Fig. 3Estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from the newsgroups data with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 10$$\end{document}K=10 obtained by running the EM updates without extrapolation (top) and the CD updates with extrapolation (bottom). The estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L are visualized using Structure plots. The documents are arranged by newsgroup to show the correspondence between the newsgroups and the topics. Note that the ordering of the documents within each newsgroup is not exactly the same in the top and bottom plots. See E1 and E2 in Fig. 2 for related results.Fig. 4Estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from the 68k PBMC data with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 7$$\end{document}K=7 obtained by running the EM updates without extrapolation (top) and the CD updates with extrapolation (bottom). The estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L are visualized using Structure plots. To facilitate comparison, the cells were split into 5 groups based on the CD estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L; these groups roughly correspond to cell types (B cells, T cells, etc). The “T cells” group was downsampled to better visualize the other groups. Note that the ordering of the cells within each grouping is not exactly the same in the top and bottom plots. See F1 and F2 in Fig. 2 for related results Selected results on fitting topic models using Poisson NMF algorithms. In A1–F1, multinomial topic model log-likelihoods are given relative to the best log-likelihood obtained among the four algorithms compared (EM and CD, with and without extrapolation). Log-likelihood differences less than 0.01 are shown as 0.01, and circles are drawn at intervals of 100 iterations. The 1,000 EM iterations performed during the initialization phase are not shown. Plots A2–F2 compare the final estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from each of A1–F1. See also Figures 5–12 in the Appendix for additional results obtained with different settings of K. Estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from the newsgroups data with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 10$$\end{document}K=10 obtained by running the EM updates without extrapolation (top) and the CD updates with extrapolation (bottom). The estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L are visualized using Structure plots. The documents are arranged by newsgroup to show the correspondence between the newsgroups and the topics. Note that the ordering of the documents within each newsgroup is not exactly the same in the top and bottom plots. See E1 and E2 in Fig. 2 for related results. Estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L from the 68k PBMC data with \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K = 7$$\end{document}K=7 obtained by running the EM updates without extrapolation (top) and the CD updates with extrapolation (bottom). The estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L are visualized using Structure plots. To facilitate comparison, the cells were split into 5 groups based on the CD estimates of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{L}$$\end{document}L; these groups roughly correspond to cell types (B cells, T cells, etc). The “T cells” group was downsampled to better visualize the other groups. Note that the ordering of the cells within each grouping is not exactly the same in the top and bottom plots. See F1 and F2 in Fig. 2 for related results Selected results of these comparisons are shown in Fig. 2, and more comprehensive results on all four data sets, with K ranging from 2 to 12, are given in the Appendix (Figures 5–12). In almost all cases, the extrapolated CD updates converged to an MLE at least as fast as the other algorithms, and often much faster, or produced the best fit within the allotted time. The extrapolation method generally helped convergence of CD, and sometimes helped EM. Also, the per-iteration running time per was very similar in all the algorithms. Beyond this, there was considerable variation in the algorithms’ performance among the different data sets and within each data set at different settings of K. To make sense of the diverse results, we distinguish three main patterns. A1 and B1 in Fig. 2 illustrate the first pattern: EM quickly progressed to a good solution, and so any improvements over EM were small regardless of the algorithm used. Indeed, despite the small improvements in log-likelihood obtained by the CD estimates in A1 and B1, the final EM and CD estimates were nearly indistinguishable from each other (Fig. 2, A2 and B2). C1 and D1 in Fig. 2 illustrate the second pattern: the initial 1,000 EM iterations were insufficient to recover estimates close to an MLE, and running additional updates sometimes substantially improved the fit. Among the four algorithms compared, the extrapolated CD updates again provided the greatest improvement in log-likelihood within the allotted time. And yet, despite the considerable improvements in log-likelihood, the final estimates did not change much (Fig. 2, C2 and D2). So while the CD updates can sometimes produce large gains in computational performance, these gains do not always have a meaningful impact on the topic modeling results. E1 and F1 in Fig. 2 are examples of the third pattern: the extrapolated CD updates not only produced estimates with greatly improved log-likelihood, they also produced estimates that were qualitatively very different (Fig. 2, E2 and F2). In both this and the previous pattern, the EM updates progressed slowly toward a solution. But whereas this slow progress was benign in the previous examples, with little impact on the final result, in these examples the slow progress of EM was in an area of the likelihood that was very far away from an MLE. We also observed an example of this pattern earlier in the MCF-7 data set (Fig. 1). In brief, the slow convergence of the EM updates is sometimes benign, and sometimes not, but it is impossible to know in advance which it is without making these comparisons. Therefore, one way to avoid this problem is to use the CD updates, which are generally better at not getting stuck in areas of the likelihood far away from an MLE. We also examined the topic model estimates in E and F to understand how the improved estimates can affect our understanding of the data. In the newsgroups data, topics 1 and 8 changed most between the EM and CD estimates (Fig. 3): in the EM estimates, the rec.auto and rec.motorcycle newsgroup discussions were largely captured by topic 1, a topic that was also shared by most other newsgroups; in the CD estimates, topic 8 distinguished rec.auto and rec.motorcycle from the other newsgroups, and topic 1 was present more evenly in all the newsgroups. In the 68k PBMC data (Fig. 4), there were many differences between the EM and CD estimates, but the changes to topic 4 most affect our understanding of these data: in the EM estimates, the T cells shared topic 4 with a subset of myeloid cells—suggesting some sort of pathway or gene expression program common to myeloid and T cells—but in the improved CD estimates, this connection between myeloid and T cells mostly disappeared, and topic 4 was mostly distinct to T cells. Concluding remarks In this paper, we suggested a simple strategy for fitting topic models by exploiting the equivalence of Poisson NMF and the multinomial topic model: first fit a Poisson NMF, then recover the corresponding topic model. To our knowledge, this equivalence, despite being informally recognized early on in the development of these methods, has not been previously exploited to fit topic models. The greatest improvements in optimization performance were achieved when the Poisson NMF was optimized using a simple co-ordinate descent (CD) algorithm. While the CD algorithm may be simple, consider that, due to the “sum-to-one” constraints, it is not obvious how to implement CD for the multinomial topic model. For many statistical applications, point estimation such as maximum-likelihood estimation will suffice when the main aim is to learn a low-rank representation of the count data. (See also (Taddy 2012).) Further, focussing on point estimation simplifies numerical computation, allowing for simpler and more efficient algorithms that can be quickly applied to large data sets. We focussed on maximum-likelihood estimation, but the ideas and algorithms presented here also apply to MAP estimation with Dirichlet priors on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textbf{F}$$\end{document}F. Extending these ideas to improve variational inference algorithms for topic models (e.g., LDA) may also be of interest. Given the success of the CD approach, it may be fruitful to develop CD-based variational inference algorithms for LDA and Poisson NMF (Gopalan et al. 2015). That said, in many applications topic models are mainly used for dimension reduction—the goal being to learn compact representations of complex patterns—and in these applications maximum-likelihood or MAP estimation may suffice. Some topic modeling applications involve massive data sets that require an “online” approach (Hoffman et al. (2010); Sato (2001); Hoffman et al. (2013); Broderick et al. (2013)). Developing online versions of our algorithms is straightforward in principle, although online learning brings additional practical challenges, such as the choice of learning rate. It is well known that EM can suffer from slow convergence; recent theoretical developments shed light on this slow convergence and the conditions under which it occurs (Kunstner et al. 2021; Dwivedi et al. 2020). And so it is perhaps not surprising that the EM variant of the Alternating Poisson Regression algorithm (Algorithm 1) was also very slow in some data sets. However, we distinguished between two types of slow convergence: benign slow convergence that occurs when the EM estimates are near an MLE; and slow convergence far away from an MLE, which can result in EM estimates that are very different from an MLE, and can affect how the topics are interpreted. Several methods have been developed specifically to accelerate EM (Zhou et al. (2011); Varadhan and Roland (2008); Henderson and Varadhan (2019)), and therefore it would have been natural to apply these methods here to improve the performance of the EM updates. We actually tried two more recent acceleration methods—DAAREM (Henderson and Varadhan 2019) and the quasi-Newton method of Zhou et al. (2011)—but in our tests (results not shown) we found that both methods provided little improvement over the unaccelerated EM. Taddy (2012) also used a quasi-Newton method to accelerate EM, but did not provide any results to show that this was beneficial. The only acceleration method that consistently improved performance was the extrapolation method of Ang and Gillis (2019).