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:
- QR is supposed to be faster than SVD (especially for low rank probs)
- When matrices have 'gaps' in singular values -> QR better than SVD
- 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.
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.