Iteration Complexity of Expectation Maximization in Poisson Inverse Problems

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

Copyright © 2020 第八屆台灣工業與應用數學會年會.