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

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

2012-09-04T21:01:13Z

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!

Answer by Joseph O'Rourke for Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

2012-09-05T00:52:47Z

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.

Answer by Arthur B for Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

2012-09-05T03:36:36Z

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$$

Answer by S. Sra for Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

2012-09-05T10:20:57Z

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.

Answer by Noah Stein for Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

2012-09-05T15:40:59Z

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.

Answer by Igor Rivin for Finding an axis-aligned ellipsoid of minimal volume which contains a given ellipsoid

2012-09-05T18:35:28Z

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.