# SVD by QR and Choleski decomposition - What is going on?

Here's an algorithm I found that performs Singular Value Decomposition. I preferred this algorithm because it can be parallelized, and I don't have to calculate the huge $AA^T$ matrix when the number of rows are very large:

Let A be the matrix for which SVD has to be performed.

$A = U{\Sigma}V^T$

1) First perform $QR$ decomposition of $A$.

$A=QR$

We calculate this by performing the 2nd and the 3rd step.

2) To calculate the $R$ matrix, calculate $A^TA$ and find the Cholesky decomposition of $A^TA$.

$R = Cholesky(A^TA)$

3) Calculate the $Q$ matrix:

$Q = AR^{-1}$

4) Also, perform SVD on the $R$ matrix (a small matrix when compared to A).

$U_R{\Sigma}V^T = R$

The $\Sigma$ and $V$ matrix for $R$ will be the same as for the SVD for $A$. Now calculate the $U$ matrix:

$U = QU_R$

Now, I know the concept of SVD through eigenvectors and eigenvalues of $AA^T$ and $A^TA$, but what is going on here? Is there an intuitive explanation?

• Why do you perform steps 2 and 3? If you have the QR decomposition of $A$, you have already the $Q$ factor you recompute at step 3 (in a very inaccurate way) and $R$ is already the Cholesky factor of $A^TA$. The algorithm would work even if you completely removed the these two steps. Oct 24, 2013 at 14:21
• Oh, I don't calculate the QR decomposition in the first step. What I meant was that I perform QR decomposition by doing step 2 and 3. I'll edit the question accordingly. Oct 24, 2013 at 17:15
• Well, that's not a very good way how to compute the QR factorisation. It is even worse than the classical implementation of the Gram-Schmidt which can be pretty well parallelized. Oct 24, 2013 at 20:21
• The problem is that I'm doing this on MapReduce, and to calculate QR using Gram-Schmidt would require me to calculate the orthogonal vectors of Q iteratively and then the R matrix, which would take another MapReduce job. With the above method, I can calculate $A^TA$ in one go, then calculate R, S and V locally and then calculate U in the next MapReduce job. Anyway, I validated the output of the above algorithm with standard implementations in R and the outputs were matching. How are you saying that it is worse than anything if it gives me the required output AND I'm not worried about its time? Oct 24, 2013 at 21:19
• Yes, taking A=rand(100)^3 (in Matlab notation). Minimal singular value computed by: 1) CGS - 2 valid digits, Cholesky of $A^TA$ - 0 valid digits. Oct 24, 2013 at 22:15