What is the computational complexity of the EM algorithm?

In general, and more specifically for Bernoulli mixture model (aka Latent Class Analysis).

-

2 Answers

I do not think you can compute the complexity in the usual way. How long it takes the EM algortihm depends on the starting point, the shape of the likelihood and the stopping criterion.

-
You can do the computational cost per iteration, though. Of course, for a given problem there might be different ways of implementing the same EM procedure with different computational complexities. –  guy Nov 7 '13 at 3:21

I liked your question!

The complexity of EM depends on the structure it is being applied on, and could be quite different from one problem to another one. But, just like any computational problem, it might be worthy of rigorous analysis to find and compare the complexity in different cases.

For some of the problems it is analyzed. For example in [1] see 3.1 . Some of these problems are proved to be NP-hard, whether with EM or not. See [3,4].

-