# Computing Positive definite covariance matrix in Variational Bayes GMM

This question is about a part of variational Bayes problem for GMM. (more in Bishop, Pattern recognition and Machine learning, part $10.2.1$). We are looking for $q(\mu_k,\Lambda_k)$, so we have: $$ln q(\mu_k,\Lambda_k)=E_{-\mu_k-\Lambda_k}[lnP(\mu_k,\Lambda_k|X,Z,\mu_{-k},\Lambda_{-k},\pi)]$$ So, $$lnP(\mu_k,\Lambda_k|X,Z,\mu_{-k},\Lambda_{-k},\pi)=I(z_n=k)\sum_{n=1}^{N} ln N(x_n|\mu_k,\Lambda_k)+lnNW(\mu_k,\Lambda_k|\mu_0,\beta_0,W_0,\nu_0)$$ $$\propto\frac{-1}{2}\sum_{n=1}^{N}I(z_n=k)(-ln|\Lambda_k|+(x_n-\mu_k)^T\Lambda_k(x_n-\mu_k))+\frac{-1}{2}(-ln|\beta_0\Lambda_k|+(\mu_k-\mu_0)^T\beta_0\Lambda_k(\mu_k-\mu_0)-(\nu_0-p-1)ln|\Lambda_k|+tr(W_0^{-1}\Lambda_k))$$ We aim to find the parameters of $q(\mu_k,\Lambda_k)$,so $$=\frac{-1}{2}\sum_{n=1}^{N}I(z_n=k)(-ln|\Lambda_k|+(x_n^T\Lambda_k x_n-\mu_k^T\Lambda_k x_n-x_n^T\Lambda_k \mu_k+\mu_k^T\Lambda_k \mu_k))+\frac{-1}{2}(-ln|\beta_0\Lambda_k|+(\mu_k^T \beta_0\Lambda_k \mu_k-\mu_0^T \beta_0\Lambda_k \mu_k-\mu_k^T \beta_0\Lambda_k\mu_0+\mu_0^T \beta_0\Lambda_k\mu_0)-(\nu_0-p-1)ln|\Lambda_k|+tr(W_0^{-1}\Lambda_k)-pln|W_0|)$$ we can write the above statement as $$=\frac{-1}{2}(\mu_k^T(\sum_{n=1}^{N}I(z_n=k)\Lambda_k+\beta_0\Lambda_k)\mu_k-\mu_k^T (\beta_0\Lambda_k\mu_0+\sum_{n=1}^{N}I(z_n=k)\Lambda_k x_n)-(\mu_0^T \beta_0\Lambda_k+\sum_{n=1}^{N}I(z_n=k)x_n^T\Lambda_k) \mu_k-ln|\beta_0\Lambda_k|+\mu_0^T \beta_0\Lambda_k\mu_0-(\nu_0-p-1)ln|\Lambda_k|+tr(W_0^{-1}\Lambda_k)-pln|W_0|-\sum_{n=1}^{N}I(z_n=k)ln|\Lambda_k|+\sum_{n=1}^{N}I(z_n=k)x_n^T\Lambda_k x_n)$$ and then $$=\frac{-1}{2}(\mu_k^T(\sum_{n=1}^{N}I(z_n=k)+\beta_0)\Lambda_k\mu_k-\mu_k^T \Lambda_k(\beta_0\mu_0+\sum_{n=1}^{N}I(z_n=k) x_n)-(\mu_0^T \beta_0+\sum_{n=1}^{N}I(z_n=k)x_n^T)\Lambda_k \mu_k-ln|\beta_0\Lambda_k|+\mu_0^T \beta_0\Lambda_k\mu_0-(\nu_0-p-1)ln|\Lambda_k|+tr(W_0^{-1}\Lambda_k)-pln|W_0|-\sum_{n=1}^{N}I(z_n=k)ln|\Lambda_k|+\sum_{n=1}^{N}I(z_n=k)x_n^T\Lambda_k x_n)$$ we define $$\beta_k=(\sum_{n=1}^{N}q(z_n=k)+\beta_0)\\ m_k=\frac{1}{\beta_k}(\beta_0\mu_0+\sum_{n=1}^{N}q(z_n=k) x_n)\\ \nu_k=\sum_{n=1}^{N}q(z_n=k)+\nu_0$$ so we have $$=\frac{-1}{2}((\mu_k-m_k)^T\beta_k\Lambda_k(\mu_k-m_k)-(\nu_k-p-1)ln|\Lambda_k|\\ -m_k^T\beta_k\Lambda_km_k-ln|\beta_0\Lambda_k|+\mu_0^T \beta_0\Lambda_k\mu_0+tr(W_0^{-1}\Lambda_k)-pln|W_0|+\sum_{n=1}^{N}I(z_n=k)x_n^T\Lambda_k x_n)$$

hence for computing $W_k$ we have $$W_k^{-1}=W_0^{-1}-m_k^T\beta_km_k+\mu_0^T \beta_0\mu_0+\sum_{n=1}^{N}q(z_n=k)x_n^T x_n (*)$$ as we can see the above matrix is not positive definite, in bishop $W_k$ is defined as bellow which is positive definite $$W_k^{-1}=W_0^{-1}+N_kS_k+\frac{\beta_0N_k}{\beta_0+N_k}(\bar x_k-\mu_0)(\bar x_k-\mu_0)^T (**)$$ in which $$N_k=\sum_{n=1}^Nq(z_n=k)\\ \bar x_k=\frac{1}{N_k}\sum_{n=1}^{N}q(z_n=k)x_n\\ S_k=\frac{1}{N_k}\sum_{n=1}^{N}q(z_n=k)(x_n-\bar x_k)(x_n-\bar x_k)^T$$

I don't know how can I reach from $(*)$ to $(**)$. would you please help me?

$(\ast)\;\; W_k^{-1}=W_0^{-1}-\color{red}{m_k \beta_k m_k'} + \color{blue}{\mu_o \beta_o \mu_0'} + \color{green}{\sum_n q_{nk} x_n x_n'}$

$W_k^{-1}=W_0^{-1}+\text{all else}=W_0^{-1} - \color{red}{\text{term1}} + \color{blue}{\text{term2}}+\color{green}{\text{term3}}$

For $\color{red}{\text{term1}}$, plug in the defined value of $m_k$:

$\color{red}{\text{term1}}=\dfrac{1}{\beta_k}\left(\beta_0^2 \mu_0 \mu_0' + \beta_0 \sum_n q_{nk} \mu_0 x_n' + \beta_0 \sum_n q_{nk} x_n \mu_0' + (\sum_n q_{nk} x_n)^2 \right)$

First, note that just according to definition, we have: $\beta_k=N_k + \beta_0$.

Also, by definition, $\sum_n q_{nk} x_n=N_k \bar{x}_k$.

$\Rightarrow \color{red}{\text{term1}}=\dfrac{1}{\beta_0 + N_k}\left( \beta_0^2 \mu_0 \mu_0' + \beta_0 N_k \mu_0 \bar{x}_k' + \beta_0 N_k \bar{x}_k \mu_0' + N_k^2 \bar{x}_k \bar{x}_k' \right)$

Therefore,

$\text{all else} = \color{blue}{\beta_0 \mu_0 \mu_0'} + \color{green}{\sum_n q_{nk} x_n x_n'} - \dfrac{1}{\beta_k}\left( \beta_0^2 \mu_0 \mu_0' + \beta_0 N_k \mu_0 \bar{x}_k' + \beta_0 N_k \bar{x}_k \mu_0' + N_k^2 \bar{x}_k \bar{x}_k' \right)$

$=\dfrac{\beta_0 N_k}{\beta_k} \color{blue}{\mu_0 \mu_0'}+\dfrac{1}{\beta_k} \left( (\beta_0 + N_k) \color{green}{\sum_n q_{nk} x_n x_n'} - \color{grey}{\beta_0 N_k\mu_0 \bar{x}_k'} - \color{grey}{\beta_0 N_k \bar{x}_k \mu_0'} - N_k^2 \bar{x}_k \bar{x}_k' \right)$

$=\dfrac{\beta_0 N_k}{\beta_k} \left( \color{blue}{\mu_0 \mu_0'} -\color{grey}{\mu_0 \bar{x}_k'} - \color{grey}{\bar{x}_k \mu_0'} + \color{purple}{\bar{x}_k\bar{x}_k'}\right)- \dfrac{\beta_0 N_k}{\beta_k}\color{purple}{\bar{x}_k\bar{x}_k'} +\dfrac{1}{\beta_k} \left( (\beta_0 + N_k) \color{green}{\sum_n q_{nk} x_n x_n'} - N_k^2 \bar{x}_k \bar{x}_k'\right)$

$=\color{magenta}{\dfrac{\beta_0 N_k}{\beta_k} (\bar{x}_k-\mu_0)(\bar{x}_k-\mu_0)'} + \dfrac{\beta_0+N_k}{\beta_k} \left( \sum_n q_{nk} x_n x_n' - N_k \bar{x}_k\bar{x}_k' \right)$

$=\color{magenta}{\dfrac{\beta_0 N_k}{\beta_k} (\bar{x}_k-\mu_0)(\bar{x}_k-\mu_0)'} + \left( \sum_n q_{nk}x_nx_n'-\color{grey}{N_k \bar{x}_k\bar{x}_k'} + \color{grey}{N_k\bar{x}_k\bar{x}_k'} - N_k\bar{x}_k \bar{x}_k' \right)$

(use the definition of $\bar{x}_k$ to get: )

$=\color{magenta}{\ldots} + (\sum_n q_{nk} x_n x_n' - \bar{x}_k \sum_n q_{nk} x_n' - \sum_n q_{nk} x_n \bar{x}_k' - \sum_n q_{nk} \bar{x}_k \bar{x}_k')$

$=\color{magenta}{\ldots} + \sum_n q_{nk} (x_n - \bar{x}_k)(x_n - \bar{x}_k)'$

$=\color{magenta}{\ldots} + N_k S_k$, as required.

• Keep track of the colors. Also, the trick of adding and subtracting a term is used twice. – Salmonstrikes Mar 9 '16 at 11:29
• The 2nd time, the trick is used in conjunction with the completion of squares trick for the arithmetic mean: $\sum_n (x_n-\bar{x})^2 = \sum_n x_n^2 - n\bar{x}^2$, since the cross terms are $-n\bar{x}^2$ each. Your problem has the matrix version of this scalar trick. – Salmonstrikes Mar 9 '16 at 11:36