Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hi.

I am busy working through a paper i came accross online on portfolio optimization. The paper may be accessed on the following link: http://ssrn.com/abstract=1483412 I am struggling, in particular, with the equation 5 on page 4. I am not sure how the authors managed to derive the equation. Why are only the first and last eigenvalues used???

Any ideas would be great!!!!

Many thanks in advance.

share|improve this question
1  
Please read FAQ before posting –  Alexandre Eremenko Dec 26 '12 at 1:29

3 Answers 3

up vote 2 down vote accepted

Problem: Let $T$ be a positive definite selfadjoint operator in an $n$-dimensional inner product space $H$. Find the maximum possible angle between a vector $v\neq 0$ and its image $Tv$, expressed in terms of the eigenvalues $\theta_0^2\geq\dots\geq\theta_{n-1}^2>0$ of $T$.

Solution: We want to minimize $\cos(v,Tv)=\frac{\langle v,Tv \rangle}{\|v\|\|Tv\|}$, or equivalently, its square $\frac{\langle v,Tv\rangle^2}{\langle v,v\rangle\langle Tv,Tv\rangle}$.

Since the angle between any vector $v\neq 0$ and its image $Tv$ doesn't change if we rescale $v$, we can rescale at our wish. I choose to restrict to those $v$ such that the numerator $g(v)=\langle v,Tv\rangle$ equals 1, so now the problem is equivalent to minimizing the denominator $f(v)=\langle v,v\rangle\langle Tv,Tv\rangle$, and now there are no divisions bothering.

Critical points of this restricted function are given by the equation $df(v)=\lambda dg(v)$, where $\lambda\in\mathbb R$ is a Lagrange multiplier. We calculate

$dg(v)=\langle v,T-\rangle+\langle -,Tv\rangle=2\langle Tv,-\rangle$ and

$df(v)=2\langle v,-\rangle\langle Tv,v\rangle+2\langle v,v\rangle\langle Tv,T-\rangle=2\|Tv\|^2\langle v,-\rangle+2\|v\|^2\langle T^2v,-\rangle$.

The critical point equation can now be rewritten:

$\langle \|Tv\|^2v+\|v\|^2T^2v-\lambda Tv,-\rangle=0$

and this is true iff $\|Tv\|^2v+\|v\|^2T^2v-\lambda Tv=0$. So $v$, $Tv$, and $T^2v$ are linearly dependent when $v$ is a critical point. But we know by Vandermonde [...] that they would be independent if $v$ had nonzero projections in three eigenspaces.

So the critical points are found in the planes spanned by two eigenvectors, and then we must solve our problem for $n=2$, being only interesting the case in which the two eigenvalues are different, because otherwise $v$ will also be an eigenvector and then the angle will be zero.

Calculations seem to get a little nicer if we express $T=S^2$, by letting $S$ be the only positive selfadjoint square root of $T$, with eigenvalues $\theta_0\geq\dots\theta_{n-1}>0$. We then have $g(v)=\langle Sv,Sv\rangle=\|Sv\|^2$, and $f(v)=\|v\|^2\|S^2v\|^2$.

Also, the symmetry is greater if we work in terms of the variable $w=Sv$, so that $g=\|w\|^2$ and $f=\|S^{-1}w\|^2\|Sw\|^2$ (this is not very important). If we express $w=x v_i+ y v_j$, where $v_i$ and $v_j$ are eigenvectors of $S$ with eigenvalues $\theta_i$ and $\theta_j$ and $i>j$, the Lagrange multipliers equation can be solved after some calculations [...], finding four critical points $(x,y)=(\pm \sqrt{\frac 12},\pm \sqrt{\frac 12})$. The minimum cosine for $w$ in the plane spanned by $v_i$ and $v_j$ is then $\frac{\langle w,w\rangle}{\|S^-1w\|\|Sw\|}=\dots=\frac{\theta_i\theta_j}{2(\theta_i^2\theta_j^2)}=\frac 12 (\frac{\theta_i}{\theta_j}+\frac{\theta_j}{\theta_i})$.

Once the case $n=2$ is solved, we want to select the plane so that $(\frac{\theta_i}{\theta_j}+\frac{\theta_j}{\theta_i})$ is maximum. But the function $h(t)=t+t^{-1}$ increases in the interval $[1,+\infty)$, so the value $t=\frac{\theta_i}{\theta_j}$ should be chosen as large as possible by maximizing $\theta_i$ and minimizing $\theta_j$.

The dots "..." represent explanations that I'm omitting. Request further details as needed.

ADDED by request of the OP: The "Vandermonde principle" says that an $n\times n$ Vandermonde matrix with different rows is invertible. This implies that if a vector $v$ has nonzero components in the eigenspaces corresponding to three different eigenvalues $\lambda_0$, $\lambda_1$, $\lambda_2$, then $v$, $Tv$ and $T^2v$ are independent.

Proof: Write $v=v_0+v_1+v_2$ so that for each $0\leq i<3$ we have $v_i$ a nonzero eigenvector corresponding to eigenvalue $\lambda_i$. Then we also have

$Tv=\lambda_0v_0+\lambda_1v_1+\lambda_2v_2$ and

$T^2v=\lambda_0^2+\lambda_1^2v_2+\lambda_2^2v_2$.

Our vectors $v$, $Tv$ and $T^2v$ belong to the subspace $S$ with basis $B=(v_0,v_1,v_2)$. And the coordinates of $v$, $Tv$ and $T^2v$ in basis $B$ are

$[v]_B=\left(\begin{array}{c}1\\1\\1\end{array}\right)$

$[Tv]_B=\left(\begin{array}{c}\lambda_0\\ \lambda_1\\ \lambda_2\end{array}\right)$

$[T^2v]_B=\left(\begin{array}{c}\lambda_0^2\\ \lambda_1^2\\ \lambda_2^2\end{array}\right)$

These are the columns of a Vandermonde matrix, so they are linearly independent, and so must be the vectors $v$, $Tv$, $T^2v$.

share|improve this answer
    
Hi Marcos Many thanks for your response. Please can you explain the "Vandermonde" principal further as I have not come across this before??? –  Geraldine Bailey Jan 3 '13 at 22:35
    
Hi Marcos...I was also wondering if you had any idea what equation 6 on page 4 means? Thanks –  Geraldine Bailey Jan 16 '13 at 8:11

This is only a partial, heuristic answer, but if you let $A$ be the square root of $\sigma$, then $\cos(\omega)$ is equal to $\frac{\alpha' \alpha}{\sqrt{\alpha' A^{-1}\alpha}\sqrt{\alpha' A\alpha}}$. If we let $\alpha$ be a unit vector, the top will always be one, and the bottom will be how much $A^{-1}$ expands $\alpha$ (which is at most the inverse of the smallest eigenvalue) times how much $A$ expands $\alpha$ (which is at most the largest eigenvalue). Just feeling it out, you probably want to add the minimum and maximum eigenvectors together since it will help make each factor in the denominator small.

Geometrically, though, the formula makes a lot of sense. If the matrix is diagonalized, we are just expanding or contracting along each axis. Imagine a 2-d version of this problem, with the x-axis expanding and the y-axis contracting (or x expanding faster than y, etc.) If we take $\alpha$ to be along either axis, its image under the transformation points in the same direction. Putting the vector exactly between the two (at a 45 degree angle) maximizes the amount that it bends away from y and towards x.

In higher dimensions, we can do the same trick along each pair of axes, but it is maximized when the two axes are as different as possible.

Note: to other readers, the OP is trying to minimize the angle between a vector and its image under a fixed positive-definite symmetric matrix.

share|improve this answer
    
Hi Brian. Your ideas are so helpful. Thanks very much. I was wondering if you noticed equation 6 also on page 4? Any idea where these equations come from or how they fit into the picture??? Thanks again for your response! –  Geraldine Bailey Dec 28 '12 at 8:54
    
Equation 6 says that the vector whichs gets twisted the most is a weighted sum of the eigenvectors corresponding to the biggest eigenvalue and to the smallest. So, I was incorrect above; the vector that is 45 degrees between the two is not best; instead, you use a weighted sum (eq. 6) that is a little closer to the bigger eigenvector. –  Brian Rushton Dec 28 '12 at 14:10
    
Although, I think we are applying the inverse of the matrix, so as we apply the matrix to the vector in (6) that is close to the bigger eigenvector, it gets shrunk in that direction and stretched in the other, making it twist a lot and apparently maximizing the angle. –  Brian Rushton Dec 28 '12 at 14:11

Here's a restatement of the problem for those who don't want to find the paper referenced in the question.

We're interested in a symmetric and positive definitive matrix $\Sigma$ that has been orthogonally diagonalized as

$ \Sigma=Q^{T}\mbox{diag}(\theta_{1}^{2},...,\theta_{n}^{2})Q $

where $\theta_{1}^{2} \geq \theta_{2}^{2} \geq ... \geq \theta_{n}^{2} > 0$, and we let $\theta_{\max}^{2}=\theta_{1}^{2}$ and $\theta_{\min}^{2}=\theta_{n}^{2}$.

Also, let

$\Theta^{2}=\mbox{diag}(\theta_{1}^{2},...,\theta_{n}^{2})$.

We want to show for any nonzero vector $\alpha$,

$ \frac{\alpha^{T}\Sigma^{-1}\alpha}{\sqrt{\alpha^{T}\alpha}\sqrt{\alpha^{T}\Sigma^{-2}\alpha}} \geq \frac{\theta_{\max}\theta_{\min}}{(\theta_{\max}^{2}+\theta_{\min}^{2})/2} $

Note that you can assume without loss of generality that $\alpha$ is of length 1. (just scale the length of alpha out of everything on the left hand side of the inequaility.)

Also, by using the substitution $x=Q\alpha$, you can reduce this to a problem about the digonal matrix $\Theta$, and then reduce the matrix-vector products to sums. We then want to show for all vectors $x$ of length 1,

$ \frac{\sum_{i=1}^{n} x_{i}^{2}\theta_{i}^{-2}} {\sqrt{\sum_{i=1}^{n}x_{i}^{2}\theta_{i}^{-4}}} \geq \frac{\theta_{\max}\theta_{\min}}{(\theta_{\max}^{2}+\theta_{\min}^{2})/2} $

Unfortunately, I don't see any easy way to proceed from here.

share|improve this answer
    
You can think of the $x_{i}^{2}$ as nonnegative weights that sum to one. This opens up the whole world of the generalized mean inequality. –  Brian Borchers Dec 26 '12 at 3:44

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.