# Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

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!

-
If your friend wants an answer, he or she should post the question. – Bill Johnson Sep 5 '12 at 0:54

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]:

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.

-

So you want $$\forall x,\\, x^t (\Lambda^{-1} - \Sigma^{-1}) x \geq 0$$ $(\Lambda^{-1} - \Sigma^{-1})$ is a symmetric matrix, and the condition expresses that it must be a positive matrix too. Let $T = \Sigma^{-1}$ and $M = \Lambda^{-1}$ we want to minimize $\det(M)$ with the constraint that $M-T$ is semi-definite positive.

This constraint can be expressed by calculating the Cholesky decomposition of $M-T$, giving $n$ inequality constraints.

At this point, I would suggest resorting to quadratic programming to solve the KKT system. (See for instance this). The Cholesky algorithm can be adapted to compute derivatives in the constraints.

Edit: removed a system of equation that only relied on the (necessary) constraint $\det(M-T)\geq 0$

We can deduce a couple simple bounds. For instance, the non negativity of $M-T$ implies that all its element are themselves non negative, thus $\frac{1}{\lambda_i} \geq \Sigma^{-1}_{i,i}$ and $$\prod_i^{n} \Sigma^{-1}_{i,i} \leq \det(\Lambda^{-1}) \leq \hbox{Tr}(\Sigma^{-1})^n$$

-
+1. Nice catch regarding that typo. – David White Sep 5 '12 at 16:54
Yes, I imagine the type of bound in your edited question is more the sort my friend is looking for (I feel like I want to call him the original original poster, or OOP). How does this bound of yours compare to what he suggests in the final paragraph, i.e. the eigenvalue bound? – David White Sep 5 '12 at 18:44
It's not as good (but simpler to calculate)... I also provide a bound in the other way – Arthur B Sep 5 '12 at 19:14

For the reasons discussed in the comments to Suvrit's answer, I will assume your friend would like to minimize $\det(\Lambda^{-1})$.

The problem in question is a convex optimization problem:

\begin{align*} \text{minimize } & -\log(\det(\Lambda)) \\ \text{subject to } & 0 \preceq \Lambda \preceq \Sigma, \\ & \Lambda \text{ diagonal}. \end{align*}

Moreover, the objective function is the natural barrier functional used for interior point methods to enforce the semi-definiteness constraint on $\Lambda$. Therefore, although strictly speaking a semidefinite program (SDP) must have a linear objective, SDP solvers typically have a mode to solve problems like this. (They may also prefer to formulate the problem equivalently as the convex program maximizing $(\det\Lambda)^{1/n}$).

In MATLAB, I would suggest using an SDP parser like CVX or Yalmip to call an SDP solver like SeDuMi or SDPT3 to solve this problem numerically to your desired level of precision.

To see how many variants of this problem can also be posed as SDPs, see Section 2 of Boyd and Vandenberghe's survey.

-
This isn't my field, so I hope this isn't a stupid comment, but knowing my friend I imagine he's interested in a theoretical solution which would hold in more generality. My guess, knowing his work, is that he needs this bound as a part of a larger paper where he's trying to bound something, perhaps asymptotically in $n$. Can SDP solvers do that sort of thing or are they just for specific problems with actual numerical inputs? – David White Sep 5 '12 at 16:53
You are correct that then this method is only applicable to actual numerical instances. As such it wouldn't be of much help as far as symbolic or asymptotic results, except perhaps for forming and testing conjectures about what to try to prove. – Noah Stein Sep 5 '12 at 17:31
I added a simple bound to my answer, is this the kind of result he's looking for? – Arthur B Sep 5 '12 at 17:47

Suppose your "ellipsoid" is a line segment from $(1, 1, \dots, 1)$ to $(-1, -1, \dots, -1).$ Any "axis-aligned ellipsoid" must contain a cube of volume $2^n,$ and pretty obviously (although I haven't checked) must contain a ball or radius $1.$ while the maximal semiaxis of your ellipsoid is $\sqrt{n},$ and all the other semiaxes are of length $0.$ The volume is, of course, also $0.$ This means that your "stupid" algorithm is not so stupid -- the maximal semi axis in some sense controls the size of the smallest axis-aligned ellipsoid, up to a $\sqrt{n}$ multiplicative factor.

-

In the way it is currently written, this problem does not have a solution. Probably minimizing $\det(\Lambda^{-1})$ was meant (as mentioned by Arthur.B in his comments below). Minimizing this is equivalent to minimizing $-\log\det(\Lambda)$ subject to the prescribed constraints. This should be doable easily using standard software.

Reasoning for the original problem being not solvable.

The reason is as follows. Since we are talking in terms of $\Lambda^{-1}$, we need the constraint $\Lambda \succ 0$. The other given constraint is $x^T\Sigma^{-1}x \le x^T\Lambda^{-1}x$, which is equivalent to $\Sigma^{-1} \preceq \Lambda^{-1}$, which in turn is equivalent to (for invertible matrices) $\Sigma \succeq \Lambda$.

Now, you wish to minimize $\det \Lambda$ for a diagonal matrix $\Lambda$. We see that setting $\Lambda = \epsilon I$ (wlog), and letting $\epsilon \to 0$ (though always strictly positive) we minimize the determinant (because for a posdef matrix the determinant is always strictly positive), while easily satisfying the constraint $\Lambda \preceq \Sigma$.

In other words, the infimum is $0$, but the minimum is not attained.

-
why the negative vote? maybe you'd like to point out the flaw in the argument?? – Suvrit Sep 5 '12 at 10:30
Because the condition is $\Sigma-\Lambda \geq 0$ and you're satisfying $\Sigma-\Lambda \leq 0$? You're suggesting that a point at the origin will be contained in the ellipsoid. True but irrelevant. – Arthur B Sep 5 '12 at 11:28
@Arthur: The condition is $\Sigma^{-1} \le \Lambda^{-1}$, and since the map $X \mapsto X^{-1}$ is order-reversing, this constraint translates into $\Sigma \ge \Lambda$, which is the same as $\Lambda \le \Sigma$. And for $\epsilon$ sufficiently small, for every positive definite $\Sigma$, we can find a $\Lambda$ that is smaller than $\Sigma$. So where is the catch? – Suvrit Sep 5 '12 at 12:26
Oh I see, the original poster wrote minimize $\det(\Lambda)$, it's clearly a typo, one want to minimize $\det(\Lambda^{-1})$ – Arthur B Sep 5 '12 at 14:41
Reading over the question, and especially the example at the end I tend to agree that it was probably a typo. He was typing into an email browser, so probably didn't see the missing $^{-1}$ – David White Sep 5 '12 at 16:49