Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.