# GMM EM algorithm complexity per iteration

I was fitting GMM clusters with diagonal covariance on my data using EM with $n$ (=5e6) points, each having $m$ (=160) dimensions. I wanted to get around $k$ (=400) clusters. But this is taking a lot of time.

My question are:

• What is the per iteration complexity of GMM EM given $n$, $m$ and $k$?
• Which parameters might help me the most in reducing the runtime most while giving useful clusters?
• Also what is the suggested number of iterations required for EM to converge given this metadata? I'm currently working iterating 100 times.
• How is this affected by going from diagonal covariance to other covariances(tied covariance or full covariance)?

Over a year after this was asked, but for anyone in a similar situation my suggestion would be to use Principal Component Analysis (PCA) to reduce the number of dimensions without sacrificing too much variance. This should make your clustering less computationally intensive.

I think it is cubic in the number of dimensions - because there is a matrix inversion step while computing the E-step. Specifically, while calculating the density of each point $$(x-\hat\mu)^T\hat{\Sigma}^{-1}(x-\hat\mu)$$, we need to invert the covariance matrix. In general, it is $$O(m^3)$$.

It is linear in the number of components and number of datapoints - I agree with the justifications given in the other answers.

A general rule of thumb is that we do not look for a large number of clusters. This is because the intended purpose of clustering is to 'summarize' the data. Moreover, there are no right or wrong clusters - just that the clusters have meaningful interpretations or not - e.g. 'points in cluster 1 predominately have characteristic A while points in cluster 2 have predominately characteristic B'. So, while you may look for $$k = 400$$ number of clusters, it is important to check if you can meaningfully interpret them.

I have run GMM EM algorithm using Python's sklearn on data with $$n = 1e6$$ datapoints, $$m = 200$$ dimensions and $$k=5$$ clusters in less than 3 minutes. I believe reducing $$k$$ may help your cause of reducing the runtime in this specific case.

• I see your point but it's not so relevant in my opinion because you invert the matrix once only. – Thomas G. Dec 20 '19 at 14:13

answer: quadratically with $$m$$ (nb. dimensions), linearly with $$n$$ (nb. points) and linearly with $$k$$

One can see this easily in the fact that the main computation happens in the calculus of $$\Sigma_{c} = \sum_{i=1}^n (x_i-\mu_c)(x_i-\mu_c)'.$$

• Adding one more point gives one more iteration of the sum (linear).
• Adding one more dimension makes the matrix $$\Sigma$$ increase in size, so $$O(m)$$ more terms to compute.

Finally I would say linearly with $$k$$ (nb. of clusters) "because you compute one more matrix and vector per additional cluster" (although this was not explicit in my course).

Note that if you specify the covariance to be diagonal or spherical.