Singular Value Decomposition trouble

[TomMe]

Suppose I want to decompose $$A = \left(\begin{array}{cc}4&4\\-3&3\end{array}\right)$$.

$$A = U \Sigma V^T => A^T A = V \Sigma^2 V^T$$ and $$A A^T = U \Sigma^2 U^T$$

So 2 independent eigenvectors of $$A^T A$$ are a basis for the row space of A and 2 independent eigenvectors of $$A A^T$$ are a basis for the column space of A.

If I pick
$$v_{1} = \left(\begin{array}{cc}1/\sqrt{2}\\1/\sqrt{2}\end{array}\right)$$ $$v_{2} = \left(\begin{array}{cc}1/\sqrt{2}\\-1/\sqrt{2}\end{array}\right)$$

and

$$u_{1} = \left(\begin{array}{cc}1\\0\end{array}\right)$$ $$u_{2} = \left(\begin{array}{cc}0\\1\end{array}\right)$$

as these bases, respectively, I get into trouble. Matrix A will not equal the singular value decomposition, there will be a sign error even though these vectors truly are correct eigenvectors.

For those who know him, this is an example that prof. Strang gave during one of his video lectures but he didn't quite see where the error came from. And since he never gave a solution, I hope I can find one here.

I started thinking about this and I noticed that these 2 bases don't have the same orientation. So I tried to find a new basis for one of the 2 spaces, with respect to the eigenvalues: just change one vector into the opposite direction. But the problem now is, this only works half the time. So for the 4 new bases I found (with respect to the eigenvalues) only 2 work out the way it's supposed to.

So if I change $$u_{2}$$ to $$\left(\begin{array}{cc}0\\-1\end{array}\right)$$ everything works out. But if I change $$u_{1}$$ to $$\left(\begin{array}{cc}-1\\0\end{array}\right)$$ things get into trouble again.
Similar for $$v_{1}$$ and $$v_{2}$$.

Can anyone tell me what is going on here?

Phew, that was a lot of typing. :tongue2: I hope I didn't make any errors, but my main point is there and that's what counts.

Thanks in advance.

 

[TomMe]

Hm, I guess this is not a popular subject then..

 

[mathwonk]

checking other people errors is seldom entertaining work.

i for one do not understand your language. what is a "singular value" decomposition? is a singular value what everyone else calls an eigenvalue?

im too lazy to read your post until i understand it in my own language.

 

[TomMe]

I understand. Just thought this was a well known topic and people would immediately recognize what the problem is. Strange.

http://en.wikipedia.org/wiki/Singular_value_decomposition

 

[mathwonk]

if you would try to answer some of my questions i would try to answer yours.

 

[TomMe]

I cannot explain it better than on the webpage I linked to.

Singular values appear to be the positive square roots of the eigenvalues of $$A^T A$$ and $$A A^T$$ for any sized matrix A. I think they play a similar role to eigenvalues for square matrices.

I think SVD is a relative new subject. It factors a matrix out into 2 different orthogonal square matrices and one m by n diagonal matrix (which can contain zeros on the diagonal).
It takes an orthogonal basis in the row space to an orthogonal basis in the column space with the entries on the diagonal matrix as multiplying factors.

Hope this was helpful..

 

[marlon]

TOM

what do you study ?

marlon

 

[George Jones]

The decompositions $A^T A = V \Sigma^2 V^T$ and $A A^T = U \Sigma^2 U^T$ are not enough to determine the decomposition $A = U \Sigma V^T$. As you have found, there are sign ambiguities. For example, if $U$ is replaced by $U' = -U$, then $U'$ still consists of normalized eigenvectors of $A A^T$, but $A$ goes to $-A$.

According to the "Geometric meaning" section of the Wikipedia website, you need to have that $Av_i$ is a non-negative multiple of $u_i$. This is true for your $v_1$ and $u_1$, but it is not true for your $v_2$ and $u_2$.

Regards,
George

 

[mathwonk]

Tomme, the point is that even if the webpage explains it well to me, it would be better for you if you tried to understand it well enough to explain it yourself. then you would be on your way to answering your own question.

 

[mathwonk]

well you got my interest. actually iw as not famkiliar with that theorem, and even found it almost unbelievable at first. for example it says geometrically that a linear isomorphism from R^2 to R^2, even if it is not length or angle preserving, nonetheless takes SOME orthogonal basis of R^2 to another orthogonal basis of R^2. NOT orthonormal!


for instance if the standard basis e1,e2, goes to e1, e1+e2, then the image vectors make an angel of 45 degrees. But if we rotate the basis {e1,e2} counterclockwise, then by the time they get to the position of {e2,-e1} their images make an angle of 135 degrees. so at some intermediate point their images were perpendicular.

so the point is that if the map is "orthogonal" ie length and angle preserving, there is no rpoblem. if on the other hand it does not preserve angles, then the images of different orthognal bases make enough different angles with each other that you can arrange it so those images are orthogonal.

of course you cannot arrange it so the images make angle zero with each other so probably what you can do is achieve an arc of angles symmetrical about the angle 90 degrees. just a guess.


does this help?

 

[TomMe]

Thanks George! That explains it! :rofl:
I'm not sure if I would have seen this myself eventually. Like you guessed, I was stuck on the $A A^T$ and $A^T A$..

TOM

what do you study ?

marlon

I am aiming to become a physicist, but at the moment I'm not sure how to do this. Tried a few times as full time student, but the stress got to me and I dropped out. But that doesn't stop me from studying meanwhile.

Tomme, the point is that even if the webpage explains it well to me, it would be better for you if you tried to understand it well enough to explain it yourself. then you would be on your way to answering your own question.

That's true. I think I did a good job of explaining it myself there. But I didn't make the connection.

Thanks both.

 

[mathwonk]

it should be clear also from my post that if one finds an orthonormal basis v,w that is mapped to an orthogonal basis {f(u), f(w)} then the orthonormal basis one wants to take in the target is f(u)/|f(u)| and f(w)/|f(w)|, and not minus these.

 

[TomMe]

Sorry, didn't see your second post there mathwonk. I must say I'm not yet familiar with the term isomorphism, it's in my course text but haven't covered it yet. So I read your post 3 times.. :shy:

But I think I understand what you mean. I'm going to try this out tomorrow with a couple of vectors (bit tired now), just for fun. Thanks for the input.

 

[mathwonk]

from a zen-like perspective, we know there is a spectral theorem diagonalizing symmetric matrices, and in fact for every matrix M, the product MM* is symmetric. so ask yourself what the diagonal form of MM* says about M itself? i.e. what do the eigenvectors of MM* mean for M?

(I have not done this, but it would be my natural next question. i am sure that understanding this is key to understanding this SVD theorem, which does not seem deep, once one knows the spectral theorem.)

 

[johnhenry11]

"BEYOND SVD"



"Advanced Eigenvalue Vector Decomposition"


We have made a significant improvement to the Singular Value
Decomposition methodology, This is actually an understatement.

We have discovered that the current Singular Value Decomposition mathematical techniques and resulting FORTRAN and C code is quite slow and inaccurate and what we have accomplished is to speed up computer execution by more than a factor of 1000 and to improve numerical accuracy by about 12 bits out of 48 bits for the standard double mantissa That is to say that there is no more than 1 bit different between the exact answer and my new solution method .Previous or current methods can barely achieve 24 bit accuracy (out of48).This improvement will make it possible to recognize red, green , blue, black, grey and white infrared images in real time as the first application .


The range of applications for this new technology can go well
beyond this.

Of course, we expect skeptics about these claims, but we have demo
programs that will read your data and produce results that they can compare and we can even executed this new code on their computers if they desire.



How AEVD Improves SVD Performance



AEVD Technology, LLC offers a fully developed, advanced form of the Singular Value Decomposition (SVD) algorithm, which offers a generational advance in speed and accuracy. Our Advanced Eigenvalue Vector Decomposition (or AEVD) was built upon a recognition of the shortcomings in how computers manipulate numbers, data and calculations, and reflects a painstaking analysis of the incremental steps in SVD processing to provide a faster process with fewer steps and improved inaccuracy.



The SVD mathematical proposition is linearly independent, in an algebraic sense, of the similarity theorem and as such provides a variety of available solution paths. One such path is to first reduce the input array to a real bidiagonal matrix with a sequence of intermediate left and right unitary transformations. This reduction to a real bidiagonal matrix is usually chosen to be a real diagonal and having one real super diagonal. All of the remaining matrix elements are numerically considered as zero. It is possible to choose other reduced forms of the input matrix, but the use of a real bidiagonal array provides for the most numerically accurate and computationally rapid solution. Additional numerical stability and computer accuracy is obtained by AEVD by choosing unitary transformations that place the larger bidiagonal elements in the upper left and the smaller elements in the lower right positions. This is true since the final determination of the left and right transformations and the SVD weights are always an iterative process for matrix sizes greater than four. Even for matrix sizes of four and less iterative methods are usually simpler and require computational steps comparable to closed form algebraic solutions. Also, when a real bidiagonal array format is chosen as the final iterate, the left and right transformations employed during iteration are orthogonal matrices. Other SVD iterative solution methods available employ orthogonal variations such as Jacobi rotation, Givens, and Householder reduction algorithms. Consistent among the more efficient and accurate SVD algorithms is the choice of the real




Regards,
John Rawlins

678-776-1343

 

[Dickfore]

@OP:

The eigenvectors of a matrix that is not Hermitian are not necessarily orthogonal. You need to use:
$$A = U \, \Sigma \, U^{-1}$$
where $U$ is a matrix whose columns are the eigenvectors.

 

[Dickfore]

Oh, I see. The matrix $A_{m \times n}$ is not necessarily square. Ok, the matrices:
$$B_{n \times n} = A^{\dagger}_{n \times m} \, A_{m \times n}$$
and
$$C_{m \times m} = A_{m \times n} \, A^{\dagger}_{n \times m}$$
are Hermitian (ex: $B^{\dagger} = (A^{\dagger} \, A)^{\dagger} = A^{\dagger} \, (A^{\dagger})^{\dagger} = A^{\dagger} \, A = B$). These can be diagonalized:
$$B_{n \times n} \, U_{n \times n} = U_{n \times n} \, \Lambda_{n \times n}, \; U^{\dagger} \, U = U \, U^{\dagger} = 1_{n \times n}$$
$$C_{m \times m} \, V_{m \times m} = V_{m \times m} \, K_{m \times m}, \; V^{\dagger} \, V = V \, V^{\dagger} = 1_{m \times m}$$

Furthermore, the eigenvalues are non-negative:
$$\lambda_{i} = \Lambda_{ i i} = (U^{\dagger} \, B \, U)_{i i} = (U^{\dagger} \, A^{\dagger} \, A \, U)_{i i} = ((A \, U)^{\dagger} \, (A \, U))_{i i} = \sum_{k = 1}^{m}{|A \, U|^{2}_{k i}} \ge 0$$
The eigenvalue $\lambda_{i}$ is zero iff the i-th column of U is in the (right) null space of A. Similarly, the eigenvalue $\kappa_{k}$ is zero iff the row of $V^{\dagger}$ is in the (left) null space of A.

 

[Dickfore]

Next, take:
$$A \, B \, U = A \, U \, \Lambda$$
$$(A \, A^{\dagger}) \, (A \, U) = (A \, U) \, \Lambda$$
$$C \, (A \, U) = (A \, U) \, \Lambda$$
$$V \, K \, (V^{\dagger} \, A \, U) = (A \, U) \, \Lambda$$
$$K \, (V^{\dagger} \, A \, U) = (V^{\dagger} \, A \, U) \, \Lambda$$

We didn't show this, but:
$$\kappa_{k} = K_{k k} = (V^{\dagger} \, C \, V)_{k k} = (V^{\dagger} \, A \, A^{\dagger} \, V)_{k k} = ((V^{\dagger} \, A) (A^{\dagger} \, V))_{k k} = \sum_{i = 1}^{n}{|V^{\dagger} \, A|^{2}_{k i}}$$
so the set of eigenvalues of $\Lambda$ and $K$ are subsets to each other.

This is why:
$$V^{\dagger} \, A \, U = \Sigma_{m \times n}$$
where $\Sigma_{m \times n}$ is a diagonal with 1's along the main diagonal (as long as it streches).
Then, we have:
$$A = V_{m \times m} \, \Sigma_{m \times n} \, U^{\dagger}_{n \times n}$$

 

[Dickfore]

I have some mistake in the deduction for the diagonal elements of $\Sigma$.