# QR(pivot) vs SVD for low rank approximation

Define the low rank problem as finding the approximation of matrix A, B: where we want to minimize rank(B) and we want the 2 norm of the residu of A-B to be less than epsilon.

Could someone help me understand what the benefits of both methods are when you use them for low rank approximation?

I did some research and found some points:

1. QR is supposed to be faster than SVD (especially for low rank probs)
2. When matrices have 'gaps' in singular values -> QR better than SVD
3. When there are no gaps in singular values, SVD is preferred.

I have no idea why 1) holds. I also have only a guess of why 2) works: the gap in singular values could make our estimation of the new matrix off because if epsilon should fall between a huge gap of singular values, the matrix we would obtain would be too rough of an approximation (we lose data we did not anticipate) ?

Another point I'd like to understand better is that I found somewhere that SVD would work better than QR when lower k was required. The example that was given was as follows:

A matrix with rank only 1:

\begin{bmatrix}1&1\\2&2\end{bmatrix}

A matrix with theoretical rank of 2:

\begin{bmatrix}1.000&0.9999\\2&2\end{bmatrix}

And a matrix $\sum$ was given from $A = U * \sum * V^T$ (SVD of A). With its singular values on the diagonal:

\begin{bmatrix}2&0\\0&10^-8\end{bmatrix}

In this case, SVD would actually tell us that the rank of the second matrix was only 1, and not really 2. Which I guess aids in a low rank approximation? I cannot explain how this helps.

• in every case, after having estimated $u_i,v_i$ such that $A \approx \sum_{i=1}^K u_i v_i^T$ you perform a gradient descent or an alternated least squares to estimate those vectors more precisely : $\min_{u,v} ||A - \sum_{i=1}^K u_i v_i^T||^2$ – reuns Jan 23 '16 at 18:52

## 1 Answer

QR is faster to compute. As for SVD we'd need several QR factorisations to compute. SVD is proven to give the best low rank approximation out of both methods.