A friend asked me to post the following question. He's not an MO user and felt it would be better received if asked by someone who was already known to the community. This is not my area, but I'll do my best to answer questions raised in the comments. Also, please feel free to retag if you want.


"Let $\Sigma$ and $\Lambda$ be $n \times n$ positive semi-definite matrices. We say that $\Lambda$ is "conservative" for $\Sigma$ if, for all $n$-dimensional vectors $x$, we have $x^\top \Sigma^{-1} x \leq x^\top \Lambda^{-1} x$. Our problem is given $\Sigma$, can we find (and if so how) a conservative diagonal matrix $\Lambda$ that minimizes $\det \Lambda$?


To think about it geometrically, we have an ellipsoid defined by the positive semi-definite matrix $\Sigma$, and we want to bound it with an axis-aligned ellipsoid defined by the diagonal matrix $\Lambda$ that has minimal volume. I'd also be interested in knowing, for example, whether we can bound $\frac{\det \Lambda}{\det \Sigma}$ in terms of the spectrum of $\Sigma$.


One trivial $\Lambda$ that works is $\lambda\_n I$, which defines a sphere with radius equal to the largest eigenvalue of $\Sigma$. It's easy to see that this can be far too large than need, however, for example if $\Sigma$ is already diagonal (say, Diag $[1, \varepsilon,
\varepsilon, \dotsc \varepsilon]$ for small $\varepsilon$)."


EDIT: I finally found time to chat with my friend about the answers here. It turns out that there was a typo, but not the one people (myself included) guessed. The original question should have read $x^\top \Sigma^{-1} x \geq x^\top \Lambda^{-1} x$ in the second paragraph, i.e. find the smallest axis aligned ellipsoid defined by $\Lambda$ containing the one defined by $\Sigma$. I've left the original question in place to avoid confusion. Those answering thought the typo was that the goal is to minimize det $\Lambda^{-1}$ instead of det $\Lambda$, and based on this they solved the related problem of finding the largest axis aligned ellipsoid contained inside the ellipsoid defined by $\Sigma$. Anyway, the good news is that the answers here did help my friend with his problem (which is highly related to the problem the answers solved), so I'm upvoting everyone and accepting the answer which I think helps most. Thanks to everyone for comments and answers!



Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid
If you can generate sufficiently many points $S$ to "delimit" the ellipsoid
defined by $\Sigma$, then the results of
this paper yield an approximation algorithm:


* Kumar & Yildirim, "Computing Minimum Volume Enclosing Axis-Aligned Ellipsoids,"
*Journal of Optimization Theory and Applications*, 136 (2), pp. 211 - 228 (2008)
[[journal link](http://www.optimization-online.org/DB_HTML/2006/06/1419.html)]:



> 
> **Abstract**: Given a set of points $S = \{x^1,\ldots,x^m\} \subset \mathbb{R}^n$ and $\epsilon > 0$, we propose and analyze an algorithm for the problem of computing a $(1 + \epsilon)$-approximation to the the minimum volume axis-aligned ellipsoid enclosing $S$. We establish that our algorithm is polynomial for fixed $\epsilon$. In addition, the algorithm returns a small core set $X \subseteq S$, whose size is independent of the number of points $m$, with the property that the minimum volume axis-aligned ellipsoid enclosing $X$ is a good approximation of the minimum volume axis-aligned ellipsoid enclosing $S$. Our computational results indicate that the algorithm exhibits significantly better performance than that indicated by the theoretical worst-case complexity result.
> 
> 
> 


