In practice, if the target rank is selected to be \(k\) , then one should sample the range of \(A\)  \(k+l\)  times where \(l\)  is a small interger. Typically \(l=10\)  is more than sufficient [1]}. In \(\mathtt {RSVD}\) , \(\Omega \)  is chosen to be a standard Gaussian matrix. Surprisingly, the computational bottleneck of \(\mathtt {RSVD}\)  is the matrix-vector multiplication in computing \(A\Omega \)  in step 4. To reduce the computational cost of this step, we can choose other types of random matrices such as the subsampled random Fourier transform (SRFT) matrix which reduces the flop count from \(O(mn(k+l)\)  to \(O(mn\log (k+l))\)  without incurring much loss in accuracy (we extend our results to this setting in Appendix REF ). It should be further noted that the computation of \(A\Omega \)  is trivially parallelizable.
