Calculating Randomized Singular Values has two main steps

27 Views Asked by At

I am learning how calculating Randomized Singular value works from a text book.

They describe it in 3 steps. Let's say $X \in R^{m \times n}$ and we'd like to find a randomized svd for it.

  1. We believe it can be captured by a low rank space with dim r, which we call Z. Sample $P \in R^{n, r}$ $$ \begin{equation} Z = X P \end{equation} $$

  2. calculate $QR$ decomposition for $Z$.

  3. Use Q matrix for change of basis (i.e. calculate $Y = Q^T X$) then calculate the svd for Y. Then for each $U_y$ as a eigenvalue of Y, use Q to lift it back to a $m$ dimensional vector and use. thus $$ \begin{equation} U_x = Q U_Y \end{equation} $$

My question is that, since Q and $Q U_Y$ are from same dimension and both orthonormal matrixes, why don't we just stop at step two and won't use Q as the $U_X$.

I am mostly looking for a intuitive answer rather than exact proof.