I'm trying to find a numerical solution to the following optimization problem $$ \text{maximize } f(M) = \frac{1}{2} \log \det(M) + \log \sum_{i=1}^n \exp \left\{ - \frac{1}{2} x_i^T M x_i + a_i \right\} \\ \text{subject to } M \preceq A, $$ where $A, x_i, a_i$ are all given. Unfortunately, log-det is concave and log-sum-exp is convex.

Edit: I think some background might help. The origin of the objective function is the following function $$ f(V) = \sum_{i=1}^n w_i \, \mathcal{N}(x_i | \, 0, V) $$ where $\mathcal{N}(x_i| \, 0, V)$ is the density of a multivariate normal distribution with mean 0 and covariance matrix $V$ (then I took the log to see if that helped). I basically want to find $V$ that maximizes the expression above subject to a constraint.

Any pointers or references to any algorithm or heuristic would be much appreciated, thanks!

  • 1
    $\begingroup$ You can rewrite $f$ as $\log(\sqrt{\det} \sum \exp)$ and since $\log$ is monotone the problem reduces to optimize $\sqrt{\det} \sum \exp$ if this helps. $\endgroup$ – Winther Aug 11 '14 at 20:36

Seems similar to the covariance update for the mixture of Gaussians model. Standard method is to use expectation-maximization (EM). It would be maximizing a lower bound, and only finds a local maximum.

  • $\begingroup$ Actually, this might not work... $\endgroup$ – Memming Aug 16 '14 at 16:33
  • $\begingroup$ Thanks for your suggestion! I agree, this kind of looks like a mixture of Normals where the weights and means are given and all the mixture components have the same covariance $V$. Why do you think EM wouldn't work here? $\endgroup$ – Shiwen Yao Aug 16 '14 at 17:13

You made mistake taking logariphm from multivariate likelihood. $\log(\det(M)$ should go with the minus sign.Thus everything is convex.Derivative of $\log(det(M)^\prime_M=M^{-1}$. Additionally it must be mulitplier $N$ here. Derivative of $\sum_i x_i^TMx=\sum x_ix_i^T$. So you final optimal solution will be $M= (\sum x_ix_i^T/N)^{-1}$ - the inverse of covariance matrix as it should be.

EDITION. I made mistake because forgot that $M$ is inverse of covariance matrix. So $\log(det(M)$ comes with the correct sign. However, likelihood is a product of exponents and loglikelihood is logarihtm of product of exponents rather the logarithm of sum exponents. So fianlly you jave concave + linear function which has the perfect maximum.

This is a wrong idea to make summation of logarithm of distributions. We have to take the logarithm of product with leads to sum of logarithms.

More precisely the correct way to look for optimal covariance matrix is try to maximize of $\Sigma$ the following mulitvariate loglikelihood $$ \prod_i \frac{1}{\sqrt{(2\pi)^k|\boldsymbol\Sigma|}} \exp\left(-\frac{1}{2}{\mathbf x_i}^T{\boldsymbol\Sigma}^{-1}{\mathbf x_i} \right), $$ If your have weights then $$ \prod_i \frac{1}{\sqrt{(2\pi)^k|\boldsymbol\Sigma|^{w_i}}} \exp\left(-w_i\frac{1}{2}{\mathbf x_i}^T{\boldsymbol\Sigma}^{-1}{\mathbf x_i} \right), $$ Taking logarithm you will get the weighted loglikelihood.

  • $\begingroup$ Why should there be a minus sign? $M$ is the precision matrix (inverse of the covariance). Also, note that this is not a product of normals, but a sum of normals. I don't see why it follows directly that the maximizer is the sample covariance matrix, and it isn't very intuitive since there are weights $w_i$. I might be wrong, but I don't see why this is a concave problem right away. $\endgroup$ – Shiwen Yao Aug 13 '14 at 21:03
  • $\begingroup$ Ohh, yes you are right, I forgot you are working with inverse of covariance. But still you have a mistake here. Not log of sum of exponent but logarithm of product.So ii is linear in $M$. Consider for the sake of simplicity scalar case $N log(m)+\sum m x_i^2$ has perfect maximum. Weights IMHO will lead to the weighted sum. They are not presented in your utility function but should as power of exponent. because the weight of observation is equivalent to mulitplication of the number of observations $\endgroup$ – Alexander Vigodner Aug 13 '14 at 21:58
  • 1
    $\begingroup$ Thanks for your answer, but I'm not doing ML estimation for a sample of Multivariate Normal observations, which is the problem you're solving in your answer. The sum of pdfs is correct -- it should not be a product. $\endgroup$ – Shiwen Yao Aug 13 '14 at 22:32
  • $\begingroup$ Of course you can do whatever you want but you will never get your covariance matrix back in such way. BTW what you wrote is not a sum of pdfs . This is logarithm of sum of pdfs which does not make any statistical sense at least for me. $\endgroup$ – Alexander Vigodner Aug 13 '14 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.