Solving for v = sum of all eigenvectors

[phaedo]

Consider a matrix A in Rⁿ with eigenvectors v_i and eigenvalues \lambda_i

 

Does anyone know of an efficient method to solve for the vector v := v₁ + ... + v_n in one go (rather than doing the whole spectral decomposition)?

 

(I am especially interested in the case where A is real symmetric)

 

Thanks

 

p

[DrRocket]

Consider a matrix A in Rⁿ with eigenvectors v_i and eigenvalues \lambda_i

 

Does anyone know of an efficient method to solve for the vector v := v₁ + ... + v_n in one go (rather than doing the whole spectral decomposition)?

 

(I am especially interested in the case where A is real symmetric)

 

Thanks

 

p

 

Corresponding to any eigenvalue there is an eigenspace, a subspace of eigenvectors, so your "sum" is not well-defined. It is not even well defined if your space comes equipped with a norm and you demand each summand be of unit length. At the very least, if v is an eigenvector, so is -v.

[ajb]

You do not mean the sum of eigenvalues, which is just the trace?

[phaedo]

Corresponding to any eigenvalue there is an eigenspace, a subspace of eigenvectors, so your "sum" is not well-defined. It is not even well defined if your space comes equipped with a norm and you demand each summand be of unit length. At the very least, if v is an eigenvector, so is -v.

 

Right, I understand your point... The analogy I have in mind is the canonical "all-ones" vector e = (1, 1, ..., 1) in Rⁿ which is the sum of the canonical basis (e_i), and somehow I want to find the corresponding "all-ones" vector v whose coordinates are (1, 1, ..., 1) in "the" (normalized) eigenbasis. But you are reminding me there are still 2ⁿ of them.

 

What I really want is to mazimize the value of (x^T A v)² for fixed x over all possible such v's... I guess this becomes some sort of discrete optimisation problem, I'll keep thinking about it

 

Thanks

 

p

 

You do not mean the sum of eigenvalues, which is just the trace?

 

No I do mean "the" sum of eigenvectors -- but there may be some connection with the trace...

Edited May 18, 2011 by phaedo

[DrRocket]

What I really want is to mazimize the value of (x^T A v)² for fixed x over all possible such v's... I guess this becomes some sort of discrete optimisation problem, I'll keep thinking about it

 

 

Since [math](x^T A \alpha v)^2 = \alpha^2(x^TAv)^2[/math] for any scalar [math]\alpha[/math] there will be no maximium unless the quadratic form is degenerate and [math](x^TAv)=0 \ \ \forall v[/math]

 

If [math]A[/math] is positive-definite and you require that both [math] x[/math] and [math]v[/math] be unit vectors in the norm associated to the inner product [math]<x,v>=x^TAv[/math] then the problem reduces to an application of the Schwartz inequality and a maximum is realized for [math]v = \pm x[/math] .

 

If [math]A[/math] is not positive-definite then, off the top of my head, I'm not sure what can be said. You might take a look at the general subject of quadratic forms.

 

What is the source of the question ?

[phaedo]

Since [math](x^T A \alpha v)^2 = \alpha^2(x^TAv)^2[/math] for any scalar [math]\alpha[/math] there will be no maximium unless the quadratic form is degenerate and [math](x^TAv)=0 \ \ \forall v[/math]

 

If [math]A[/math] is positive-definite and you require that both [math] x[/math] and [math]v[/math] be unit vectors in the norm associated to the inner product [math]<x,v>=x^TAv[/math] then the problem reduces to an application of the Schwartz inequality and a maximum is realized for [math]v = \pm x[/math] .

 

If [math]A[/math] is not positive-definite then, off the top of my head, I'm not sure what can be said. You might take a look at the general subject of quadratic forms.

 

What is the source of the question ?

 

Thanks a lot for your interest in my problem.

 

Yes A is pos-def

 

The v I was mentioning in [math](x^T A v)^2[/math] was my "all-ones vector" in any of the 2ⁿ normalized eigenbases, so the Schwartz inequality won't give the answer

 

The idea is to get a better lower bound than [math]\lambda_{\text min}[/math] for the Rayleigh ratio [math] R(x) := \frac{x^T A x}{x^T x} [/math] for fixed x, and the whole things is part of a larger problem in quant finance that would be too long to expose here. It can be shown that [math]R(x) \geq \frac{(x^T A v)^2}{x^T x}[/math], and I'd like to find "this" v without doing the whole spectral decomposition thing...

 

p

[DrRocket]

Thanks a lot for your interest in my problem.

 

Yes A is pos-def

 

The v I was mentioning in [math](x^T A v)^2[/math] was my "all-ones vector" in any of the 2ⁿ normalized eigenbases, so the Schwartz inequality won't give the answer

 

The idea is to get a better lower bound than [math]\lambda_{\text min}[/math] for the Rayleigh ratio [math] R(x) := \frac{x^T A x}{x^T x} [/math] for fixed x, and the whole things is part of a larger problem in quant finance that would be too long to expose here. It can be shown that [math]R(x) \geq \frac{(x^T A v)^2}{x^T x}[/math], and I'd like to find "this" v without doing the whole spectral decomposition thing...

 

p

 

 

If A is positive definite then [math]<x,y> = x^TAy[/math] is an inner product in the usual sense of linear algebra (a positive-definite bi-linear form). If you now define [math] ||x|| = \sqrt {<x,x>}[/math] then the Schwartz inequality is [math] |<x,y>| \le ||x|| \ ||y||[/math] with equality if and only if [math]x[/math] and [math]y[/math] are linearly dependent.

 

So to maximize [math] \frac{(x^T A v)^2}{x^T x}[/math] for fixed [math]x[/math] one has to maximize [math](x^T A v)^2 = (<x,v>)^2[/math] which by the Schwartz inequality is bounded by [math](||x|| \ ||v||)^2[/math] with the bound achieved if and only if [math]v[/math] is a scalar multiple of x. Now you just have to decide what constraints your problem imposes on the scalar.

[phaedo]

@DrRocket: my v isn't a free vector, it is the all-ones vector in on of the eigenbases...

[DrRocket]

Thanks a lot for your interest in my problem.

 

Yes A is pos-def

 

The v I was mentioning in [math](x^T A v)^2[/math] was my "all-ones vector" in any of the 2ⁿ normalized eigenbases, so the Schwartz inequality won't give the answer

 

The idea is to get a better lower bound than [math]\lambda_{\text min}[/math] for the Rayleigh ratio [math] R(x) := \frac{x^T A x}{x^T x} [/math] for fixed x, and the whole things is part of a larger problem in quant finance that would be too long to expose here. It can be shown that [math]R(x) \geq \frac{(x^T A v)^2}{x^T x}[/math], and I'd like to find "this" v without doing the whole spectral decomposition thing...

 

p

 

 

OK, I'm lost.

 

If x is fixed then [math] \frac{x^T A x}{x^T x} [/math] is just a number. If x varies over the vector space then

[math]\lambda_{\text min}[/math] is the greatest lower bound and [math]\lambda_{\text max}[/math] is the least upper bound of [math] \frac{x^T A x}{x^T x} [/math].

 

In order to make sense of your "all one's" vector it is necessary that the eigenvalues of A be distinct. So let's assume that. Since A is symmetric it follows that eigenvectors corresponding to disrinct eigenvalues are orthogonal. Thus your space has an orthonormal basis of eigenvectors of A say [math]v_1,...,v_n[/math] and this basis is determined up to [math]\pm v_1,..., \pm v_n[/math]. So now you are trying to maximize [math]|<x,\lambda_i v_i>|=\lambda_i |<x,v_i>|[/math] for some fixed x.

 

I see no way to do this without expressing x in terms of the [math]v_i[/math] which is equivalent to knowing each [math]<x,v_i>[/math]. In fact one can concoct an x to make [math] \frac{x^T A x}{x^T x} [/math] anything that you like between [math]\lambda_{\text min}[/math] and [math]\lambda_{\text max}[/math] with a convex combination of the [math]v_i[/math].

 

Essentially you have an [math]x = a_1v_1+...+a_nv_n[/math] normalized so that [math] \sqrt {a_1^2+...+a_n^2} = 1[/math] and you are looking for the maximum of [math]|<x,v_i>|= |a_i| \lambda_i[/math]. This requires knowing all of the [math]a_i[/math]

[phaedo]

So now you are trying to maximize [math]|<x,\lambda_i v_i>|=\lambda_i |<x,v_i>|[/math] for some fixed x.

 

I 'm sorry if I wasn't clear. I am well-aware that R(x) has tight bounds [math]\lambda_{min} \leq R(x) \leq \lambda_{max}[/math] over all x, but here x is fixed and the lower bound [math] (x^T A v)^2/x^T x[/math] I'm interested in depends on x, so it may well be better than [math]\lambda_{min}[/math] in some cases.

 

I am trying to maximize [math]\textstyle \left( \sum_i \lambda_i x^T v_i \right)^2[/math] over all 2ⁿ possible choices of eigenbases (v_i), not each [math]\lambda_i |x^T v_i|[/math] as you suggest. I'd like to find the optimal "all-ones" vector v^* without having to solve for each v_i.

[DrRocket]

I am trying to maximize [math]\textstyle \left( \sum_i \lambda_i x^T v_i \right)^2[/math] over all 2ⁿ possible choices of eigenbases (v_i), not each [math]\lambda_i |x^T v_i|[/math] as you suggest. I'd like to find the optimal "all-ones" vector v^* without having to solve for each v_i.

 

I understand.

 

What is apparently not clear in what I said is that I don't think you can do that without knowing more about x, and "knowing more" means expressing x in the orthonormal basis of eigenvectors of A -- which entails solving for each v_i.

If [math] x= a_1v_1+...+a_nv_n[/math] for some choice of the [math]v_i[/math] then your various [math]2^n[/math] possibilities for [math]\textstyle \left( \sum_i \lambda_i x^T v_i \right)^2[/math] are just

 

[math]\textstyle \left( \sum_i \pm \lambda_i a_i \right)^2[/math]

 

Maximixation is a selection of + or - for each term. That seems to me to require knowledge of each [math]a_i[/math] (really just the sign of [math]a_i[/math] but that doesn't help) which requires solving for the [math]v_i[/math].

 

I don't think you can do what you would like.

 

The only slight hope that I can see is this: quantitative finance has attracted the interest of some algebraic geometers. They might have developed an alternate approach to your fundamental problem (not this specific optimization problem but something deeper). You may want to talk to someone like that.

[phaedo]

I don't think you can do what you would like.

 

The only slight hope that I can see is this: quantitative finance has attracted the interest of some algebraic geometers. They might have developed an alternate approach to your fundamental problem (not this specific optimization problem but something deeper). You may want to talk to someone like that.

 

I think I could relax the problem a little and look for e.g. a vector v such that [math]v^T v = 1, v^T A v = tr(A)[/math]. I am aware of some of the work done in quant finance related to optimization problems, not sure this is what I'm looking for though...

 

Thanks for your very pertinent remarks.

 

p.

[DrRocket]

I think I could relax the problem a little and look for e.g. a vector v such that [math]v^T v = 1, v^T A v = tr(A)[/math]. I am aware of some of the work done in quant finance related to optimization problems, not sure this is what I'm looking for though...

 

Thanks for your very pertinent remarks.

 

p.

 

There might be a way to produce such a [mathv[/math] without finding the eignvectors of [math]A[/math] but I don't see it.

 

Good luck in your search.