Chien-Ming Lin1 and Yen-Huan Li1,2
1Department of Computer Science and Information Engineering, National Taiwan University
2Department of Mathematics, National Taiwan University
Poisson inverse problems arise in many real-world applications, such as positron emission tomograpy, astronomical imaging, and network flow analysis. Expectation maximization (EM) is a standard approach to solving a Poisson inverse problem. The asymptotic convergence of EM was established more than three decades ago. The convergence speed of EM, however, had remained unclear. We show that EM attains an $\varepsilon-approximate$ solution in $O((1 / \varepsilon) \log D)$ iterations. Moreover, we give an online algorithm for Poisson inverse problems that attains an $\varepsilon-approximate$ solution in $O( ( 1 / \varepsilon ^ 2 ) D \log D ) $iterations; we argue the algorithm is the first provably converging online version of EM. As a byproduct, we also give the first non-asymptotic analysis of a portfolio selection algorithm due to Thomas Cover (T. M. Cover. An algorithm for maximizing expected log investment return. IEEE Trans. Inf. Theory. 1984.), which is of independent interest.
Keywords：Expectation maximization, Poisson inverse problem, portfolio selection, Soft-Bayes