Re: minimization of a matrix function


In article <1183331109.000116.173210@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
hs.samix@xxxxxxxxx writes:
On Jun 30, 12:54 pm, Ron Shepard <ron-shep...@xxxxxxxxxxxxxxxxxx>
wrote:
In article <1183146043.639165.208...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,



hs.sa...@xxxxxxxxx wrote:
Hello,

I have a situation where I need to solve for vectors x_i, where X =
[x_1 x_2 . . x_d] such that

XQX' = diag{a_1, a_2, ..., a_d}
you confused X and X' here: in your notation X is N times d
hence you must build X'QX.
you also forgot to mention that you require X'X = I_d,
which gives pretty disagreeable side constraints



where Q is a square, real and symetric NxNmatrixand X' denotes
transpose of X and a_i's are scalars. Also, d << N.

I see that one way is tominimizethe following:

XQX' - diag{a_1, a_2, ..., a_d}

to obtain the solution X*.

Any suggestion which optimization algorithm I should try? I am looking
at Levenberg-Marquardt for now. Its C implementation is given here:
http://www.ics.forth.gr/~lourakis/levmar/
though I could try LAPACK and MINPACK directly if necessary.

This is not so much a minimization problem as an eigenvector
problem. It appears that you want the d lowest eigenvectors of the
real symmetricmatrixQ. There are both direct and iterative
methods to find eigenvectors of matrices -- it depends on the
structure and dimensions of thematrixQ which is best to use. You
mention amatrixfunction, which might mean that Q is really Q(z)
for some set of variables z. In this case, the eigenvectors would
be also functions of these variables z, and their functional
dependence can be determined by perturbation theory.

So, I think you need to study eigenvalue problems and perturbation
theory in order to understand the solution to your problem. The
LAPACK documentation would be a good place to start, and then follow
the references therein for more details.

$.02 -Ron Shepard


You are correct that this is an eigenvalue problem; I was trying to
keep the story short.

I am trying to find lowest d eigenvectors of matirx Q once it has been
perturbed. The idea is that the system remains the same despite the
perturbation and that the eigenvalues will also remain the same.

To solve for the eigenvectors, I am already using LAPACK. The
objective is to obtain the eigenvectors after each perturbation. The
problem is that each run of the eigensolver produces new eigenvectors
which are either scaled by a constant (- or +) or are different due to
perturbantions in Q. So instead of running the eigsolver (dsaupd
function in FORTRAN), I am trying to implement a paper which shows
that the new eigenvectors may be found by minimizing the above
problem. I am reading up on Levenberg-Marquardt algorithm to see if I
can find the eigenvectors (X in the problem statement) by minimizing
the function I mentined above.


as long as the eigenvalues stay disjoint, you could
solve the eigenvalue problem first for a given system and then
use Newtons method for the nonlinear system

[ Q x_i ] [ x_i ] = [ 0 ]
[ x_i' 0 ] [ a_i]= [ 1 ]
which would converge fast if Q has changed only little, taking the "old"
x_i, a_i as initial guess. orthogonality of eigenvectors for different
eigenvalues of the symmetric Q is automatic


Now that I have given the gist of the story, I have another question.
Lets say I have a N data points at time t X = [x1 x2 ... xN] and want
to get the eigenvectors of XX'. At time t+1, lets say the first data
point is discarded and the newest one becomes xN. I want to get the
eigenvectors again. But this time, if I run the eigensolver on the new
data's covariance matrix, I have a problem of an unknown constant (Ax
= lx where l is the eigenvalue and x is the eigenvector of A). Now as
time progresses, and I want the new eigenvectors at each time instant,
I get eigenvectors with arbitrary signs -- and this is the problem.
How do I get around this? I have researched this for a bit and haven't
really obtained any definite answer/method. Also, it would also be
helpful if someone can mention approaches which deal with this
evolution of eigenvectors based on time-dependent data. Any comments
on this?

Thanks.

this is much more involved:
this will not be a "small perturbation"
it is known as the eigenvalue
updating problem and involves a change of all eigenvalues and eigenvectors
there are special methods for this . again it is essential whether the
eigenvalues are disjoint or not
for there special literature for this
hth
peter
.

Relevant Pages

  • Re: minimization of a matrix function
    ... It appears that you want the d lowest eigenvectors of the ... I think you need to study eigenvalue problems and perturbation ... I am reading up on Levenberg-Marquardt algorithm to see if I ... can find the eigenvectors by minimizing ...
    (sci.math.num-analysis)
  • Re: Matrix Diagonalization
    ... LAPACK and virtually everything else get that one wrong! ... Run it, extracting all eigenvectors, and see :-) ... then the routine will ignore the lower triangle of the ... input and diagonalize a unit matrix of dimension 2x2. ...
    (comp.lang.fortran)
  • Re: Matrix Diagonalization
    ... LAPACK and virtually everything else get that one wrong! ... Run it, extracting all eigenvectors, and see :-) ... The all zeroes is not invalid, ... bug in the error detection; if the former, ...
    (comp.lang.fortran)
  • Re: using a lapack routine
    ... I prefer to compile LAPACK and create a library. ... module with interfaces to LAPACK subroutines. ... real symmetric matrix. ... eigenvectors of a real matrix A I type v=eigVectors, ...
    (comp.lang.fortran)
  • Re: eigenstructure from eig
    ... > If A is a symmetric matrix, ... how does it choose the eigenvectors? ... You'd need to look at the properties of your matrix A, find which LAPACK ... you'll need to check the LAPACK routines and/or the ...
    (comp.soft-sys.matlab)