# Is there a covariance MLE which takes into account independence relationships?

In the extreme case where all of the components of an $M$-variate observation are pairwise independent from each other, a multivariate normal distribution can be decomposed into the product of $M$ univariate normal distributions. For example, $$p \left( X_{1},X_{2},X_{3};[\mu_{1},\mu_{2},\mu_{3}]^{T},\left[\begin{array}{ccc} \sigma_{1} & 0 & 0\\ 0 & \sigma_{2} & 0\\ 0 & 0 & \sigma_{3}\end{array}\right]\right)=\prod_{i=1}^{3}\ p(X_{i};\mu_{i},\sigma_{i}).$$ The sample complexity of a univariate distribution is less than that of a full-covariance $M$-variate normal distribution, and thus fewer observations are required to get a good approximation of this model, since only univariate distributions must be estimated.

With zero-mean observations $\{x^{(1)},\cdots,x^{(N)}\}$, the covariance MLE for the case where the covariance matrix is isotropic (i.e. all observation components -- denoted with subscripts -- are pairwise independent) is simply $\hat{\Sigma}=\mathrm{diag}(\hat{\sigma}_{1,}\hat{\sigma}_{2},\cdots,\hat{\sigma}_{M})$ where $\hat{\sigma}_{i}=\frac{1}{N}\sum_{j=1}^{N}\left(x_{i}^{(j)}\right)^{2}$. This pairwise independence is represented as zeros in the precision matrix $\Sigma^{-1}$, which is diagonal when $\Sigma$ is diagonal. As mentioned above, this is identical to (i.e. gives the same result as) separately estimating $M$ univariate distributions, and taking their product.

My question is: In the in between case, where there is some (not fully connected) dependency graph $\mathcal{G}$ between observation components, what does the covariance MLE look like then? As a specific example, if we say that $X_{1},X_{2}\perp X_{3}$, then the precision matrix must always have the form $$\Sigma^{-1} = \left[\begin{array}{ccc} \lambda_{11} & \lambda_{12} & 0\\ \lambda_{21} & \lambda_{22} & 0\\ 0 & 0 & \lambda_{33}\end{array}\right].$$ Therefore, what would the decomposition, and the covariance (or inverse covariance) MLE look like for a normal distribution such as the following? : $$p\left(X_{1},X_{2},X_{3};[\mu_{1},\mu_{2},\mu_{3}]^{T},\left[\begin{array}{ccc} \lambda_{11} & \lambda_{12} & 0\\ \lambda_{21} & \lambda_{22} & 0\\ 0 & 0 & \lambda_{33}\end{array}\right]^{-1}\right)$$ For a given number of observations, the MLE should give the same result as the decomposed version of the pdf represented by $\mathcal{G}$.

-
@Mark, say if there was such a representation, why would you want to use it? Independent case leads to easy computation, but depending on $\mathcal{G}$ the computational complexity can be the same as without any structure assumptions. I am asking purely out of curiosity. –  mpiktas Jun 14 '11 at 9:45
This sounds like an eigen-decomposition of the covariance matrix would be the way to go. You can always represent a $M$ dimensional normal as a translated, rotated, and scaled combination of independent standard normals. Translation does not affect covariance, and scaling does not affect independence/correlations, so you could just examine the rotation matrix, which is given by the matrix of normalised eigenvectors. –  probabilityislogic Jun 14 '11 at 13:19
@Mark What do you mean by "sample complexity" and what justifies your conclusion that "fewer samples" are needed for estimation in the diagonal case? –  whuber Jun 14 '11 at 13:51
@whuber - Sample complexity, roughly speaking, is the number of samples required in order to estimate the model in a "probably approximately correct" sense. The larger the hypothesis space is (larger for an M-variate Normal distribution than for a univariate Normal distribution), the more samples will be required to achieve the same amount of "approximate correctness" to the same probability. But, in the case of conditional independence relationships, the hypothesis space size is actually smaller than for the case where no independence assumptions are made (i.e. full-covariance matrix). –  Mark Jun 14 '11 at 18:47
@whuber - sorry, I meant to say 'number of observations', and not 'number of samples'. (edited original post to reflect this -- was a minute too late to edit my previous comment :( ) –  Mark Jun 14 '11 at 18:58