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.
