Maths - Reorthogonalising a matrix Forum message from Hauke

Martin,

this post concerns a page "Maths - Reorthogonalising a matrix".

I have some ideas about correction matrix. As C is symmetric, then we can use arbitrary powers of a matrix. To calculate power of a matrix an eigenvalue decomposition can be used. Matrix is written as Q*D*Q^T, where Q is orthogonal and D is diagonal. Then any function F(that can be expanded in Taylor series) of a matrix can be calculated as Q*F(D)*Q^T, where F can be applied to D elementwise. If such method is used for computation of the correction matrix, we get exactly orthogonal matrix (except for rounding errors). But it is more computationally expensive then just using of the first two terms of Taylor expansion, though more precise. I haven't yet compared it to orthogonalization with SVD, but it seems that eigenvalue decomposition is somewhat simpler.

\>>Is this more orthogonal than the original matrix, I can't really tell, it looks as though it might be?

In the given example it seems to be so, because applying reorthogonalization to a matrix several times converges to an orthogonal matrix, and this matrix equals one computed with eigenvalue decomposition. So, using the first two terms of Taylor expansion may be not so bad if we need fast algorithm.

Thanks for this. I don't understand as much of this as I would like, so I appreciate any help.

I am not quite clear why we can set: O=C*M where:

• O is orthogonal: O^t = O^-1
• C is symmetric: C^t = C
• M is almost orthogonal but not quite.

As you say, eigenvalue decomposition looks similar to SVD:

• eigenvalue decomposition: QDQ^T
• SVD: [U][D][V]^t

The difference appears to me to be (at first sight) that SVD is a more general version of eigenvalue decomposition where U is not equal to V?

I guess I need to find out the general rules for these matrices:

• orthogonal*orthogonal=orthogonal
• symmetric*symmetric=symmetric
• orthogonal*symmetric=?

Also why any function F can be applied to Q*F(D)*Q^T

Do you know a good web source for this topic?

Thanks,

Martin

Sorry, I mistakenly supposed that we need to decompose an orthogonal matrix. So in general case the eigenvalue decomposition is A=QDQ^-1 (But not QDQ^T), where Q is not necessary orthogonal.

I am not quite clear why we can set: O=C*M where:

O is orthogonal: O^t = O^-1
C is symmetric: C^t = C
M is almost orthogonal but not quite.

We just assume that for given M, exists such symmetric C, that C*M gives us some orthogonal matrix. Then we prove that such C exists and find it. Of course, instead of symmetric matrix any other matrix can be chosen, but it is convenient for us if it is symmetric (otherwise we couldn't be able to use this method). May be some other types will give us interesting results.

As you say, eigenvalue decomposition looks similar to SVD:

eigenvalue decomposition: QDQ^T
SVD: [U][D][V]^t

The difference appears to me to be (at first sight) that SVD is a more general
version of eigenvalue decomposition where U is not equal to V?

Eigenvalue decomposition of a non-orthogonal matrix gives us QDQ^-1. If we decompose an orthogonal matrix, we get QDQ^-1=QDQ^T, where Q is orthogonal. So SVD is the general case of eigenvalue decomposition only for orthogonal matrices. In our case we have to decompose MM^T, which is not orthogonal.

I guess I need to find out the general rules for these matrices:

orthogonal*orthogonal=orthogonal
symmetric*symmetric=symmetric
orthogonal*symmetric=?

I suppose that in the latter case we can get any square matrix.

Also why any function F can be applied to Q*F(D)*Q^T

If we want to calculate the square of matrix A=QDQ^-1, then we get A^2=QD(Q^-1Q)DQ^-1=QDEDQ^-1=QD^2Q^-1. This is true for all other powers: A^n=QD^nQ^-1, where integer n>=0. If we define function of a matrix through Taylor series, then F(A)=a0E+a1A+a2A^2+...=QEQ^-1+QDQ^-1+QD^2Q^-1+...=Q(E+D+D^2+...)Q^-1=QF(D)Q^-1. This is from wikipedia, section Functional calculus.

But this is not exactly what we need. We need to find such C that (MM^T)^-1=C^2. Let us decompose MM^T=QDQ^-1, then QD^-1Q-1=C^2, (QD^-0.5Q^-1)(QD^-0.5Q^-1)=C^2. So, we can choose C=QD^-0.5Q^-1. We can raise D to power -0.5, because MM^T has real nonnegative eigenvalues, and as M is almost orthogonal, so it cannot have zero eigenvalues.

Do you know a good web source for this topic?

I can only suggest wikipedia and wolfram mathworld

Thanks very much, even though the original idea didn't work out you have given me some interesting things to think about,

Cheers - Martin