2
$\begingroup$

For an axis-aligned ellipsoid

$a_{11}x_1^2+a_{22}x_2^2+a_{33}x_3^2+a_{44}x_4^2=1$

it is easy to see that $x_1$ is in the range $-1/\sqrt{a_{11}}$ to $1/\sqrt{a_{11}}$. However, in the general case of a rotated ellipsoid,

$\sum_{i,j} a_{ij}x_ix_j=1$      (eq. 1)

where $a_{ij}$ forms a positive definite matrix, how do I calculate the limits for $x_1$?

In other words, I want to project the ellipsoid (which in my case has ~100 000 dimensions) onto its first dimension.

What I have come up with so far is solving eq. 1 wrt. $x_1$

$x_1 = \frac1{a_{11}}\left[-\sum_{j\neq1}x_ja_{1j}\pm\sqrt{a_{11}(\sum_{i\neq1, j\neq1}x_ix_ja_{ij})-((\sum_{j\neq1}x_ja_{1j})^2) }\right]$

and taking its first derivative with respect to the other $x_k$

$\frac{dx_1}{dx_k}=\frac1{a_{11}}\left[-a_{1k}\pm\frac{a_{11}x_k(\sum_{j\neq1}x_ja_{kj})-A_{1k}}{\sqrt{a_{11}(\sum_{i\neq1, j\neq1}x_ix_ja_{ij})-((\sum_{j\neq1}x_ja_{1j})^2) }}\right]$

to exploit the necessary condition $\frac{dx_1}{dx_k}=0$ for extrema. However, the resulting system of equations does not look like I could find a general solution easily, especially since all the sums still contain $x_k$ :-(.

Is there possibly a much smarter way to solve this problem? Or am I stuck with plugging the formula for $x_1$ and its derivative into a numerical solver to find minimum and maximum?

1 Answers 1

3

I'd go with Lagrange multipliers:

We want to maximize(minimize) $ {\bf e_n^T x } $ , where $ {\bf e_n^T} = (0, 0 \cdots 0 , 1, 0 \cdots 0 , 0)$ subject to the condition ${\bf x^T A x} = 1$ (${\bf A}$ symmetric)

Then, we write $\nabla({\bf e_n^T x} + \lambda \; {\bf x^T A x})=0 $ and we get $ {\bf e_n } + 2 \lambda \; {\bf A x} = {\bf 0} \Rightarrow {\bf x = }\alpha \; {\bf A^{-1} e_n}$

the constant can be obtained from the restriction ${\bf x^T A x} = 1$ (of course, we have two solutions, with opposite signs) :

$\alpha^2 = \frac{1}{\bf e_n^TA^{-1} e_n}$

so $ {\bf x} = \pm \frac{{\bf A^{-1} e_n}}{\sqrt{\bf e_n^TA^{-1} e_n}}$

Added: Notice that if we just want the value of the maximized coordinate, we get:

$ x_n = {\bf e_n^T x} = \pm \sqrt{\bf e_n^TA^{-1} e_n} = \pm \sqrt{{\bf A}^{-1}_{n,n}} $

so, the ellipse ${\bf x^T A x} = 1$ fits inside a prism of coordinates given by the square roots of the diagonal elements of the inverse matrix. This should have some geometrical interpretation, but I don't quite see it (except for the diagonal case).

  • 0
    @Jonas: So it seems2011-09-13