Re: minimization of a matrix function

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}

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.

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.

.