Re: ? determine eigenbasis and eigenvalues of A directly from X and B where A*X=B


In article <qEGTf.40161$915.30613@xxxxxxxxxxxxxxxx>,
"Cheng Cosine" <acosine@xxxxxxxxxxxx> writes:

"Peter Spellucci" <spellucci@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote in
message news:dvm7k0$i6n$1@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

In article <lKrTf.40070$915.6802@xxxxxxxxxxxxxxxx>,
"Cheng Cosine" <acosine@xxxxxxxxxxxx> writes:

...
But this needs not be A's eigenbasis. Can we determine A's eigenbasis

and corresponding scale factors DIRECTLY from matrices X and B?

Of course we can use A*X = B => A = B*inv(X) to get A and then

decomp A into A = V*D*V' but now I am asking DIRECTLY determine

V and D from X and B, or to solve V*D*V'*X = B => V =? and D = ?

in short: you have X and B, two invertible n by n matrices and know that
B is the image of X under an unknown matrix A. You want the
eigendecomposition
of A without prior computing A as B*inv(X).
well , as long as you can cheaply solve linear systems with the matrix X,
you could use the ideas of vector iteration/ simultaneous vector
iteration/
Lanczos based methods, which only require computing a Krylow subspace of
A which could be obtained from

X z_{k+1} = u_k
u_{k+1} = B z_{k+1}
as the sequence {u_k}
but these methods make little sense if you need the full decomposition as
your question suggests.

In practice only several "significant" eigenvectors are needed to provide
approx

with certain requirements. Say, an approx could be only to determine first
largest

(abs value) eigenvalues and eigenvectors. But what kind of approx is this,
or to

be more specific, in what norm? I saw two norms often appeal in Numerical
analysis:

inf-norm and 2-norm. Then if only inf-norm or 2-norm approx is required for
reconstructing

A, what is the algorithm?

Thanks,
by Cheng Cosine
Mar/20/2k6 NC




the norm has no fundamental influence here: if you have convergence in a
finite dimensional space you have convergence in any norm, because topologically
they are all equivalent here: to say it simpler: you may pack a sphere in a
cube and this in turn in a larger sphere and so on (to stay with the
inf and the 2-norm) if you want indeed the leading eigenvalues (in absolute
value) with their corresponding eigenvectors, then you could either use
simultaneous vector iteration or lanczos resp . arnoldi. from your original
question I extract that you know that A must be symmetric, hence the
"ritzit" type of iteration would be my choice. this goes as follows:
you have a n times p matrix W_0 representing the eigenvectors to the first
p eigenvalues (chose p somewhat larger than the number of eigenvalues you need)
W_0 must the orthonormalized, as the true eigenvectors are.
for you "A" is given by X and B, implied by A*X=B, hence you iterate like

solve X*Z_k =W_k
multiply Y_k =B*Z_k
compute the Householder QR-decomposition
Y_k =Q_k*R_k Q_k is n times p , R_k upper triangular p times p.
compute
R_k*R_k' = C_k
and solve the complete eigenvalue problem
C_k = U_k*Lambda_k*U_k'
and set
W_{k+1}= Q_k*U_k

the diagonal elements of Lambda_k approximate the squares of the eigenvalues
to the eigenvectors found in W_k. you extract the correct sign by
considering W_k'*Y_k . Y_k is the result of one step of the power method
applied to W_k and the following steps serve the purpose to extract an
optimal orthogonal basis from Y_k.
you can of course use the Lanczos method (with a reasonable partial or
even a total reorthogonalization. also this one requires that (in this
case tridiagonal) complete eigenvalues problems of small size must be solved.
hence all this makes sense only if
your "A" is very large
the linear system with "X" can be solved very cheaply
since otherwise direct computation of A=B*inv(X) and application of the
algorithm to A should be much more efficient.
hth
peter

.

Relevant Pages
Quantcast