# How can I analytically determine a 1D projection of a high-dimensional ellipsoid?

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?

-

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).

-
 This sounds really good, the type of solution I was hoping for :-). So basically for fixed $\bf e_n$ my work is reduced to calculating the n-th column of the inverse of $\bf A$, and determining the normalisation constant $\alpha$. – Jonas Heidelberg Sep 13 '11 at 15:56 Reading your edited answer and going to my special case, it really reduces to $x_1=\pm\sqrt{({\bf A^{-1}})_{11}}$, in other words I only need the top left element of the inverse of $\bf A$? – Jonas Heidelberg Sep 13 '11 at 16:03 @Jonas: So it seems – leonbloy Sep 13 '11 at 16:07