Understanding randomized SVD

(Austin Shin) #1

Hi, I have a few questions about the randomized SVD:

1 This line -> "Compute an approximation to the range of A. That is, we want QQT with r orthonormal columns such that A≈QQTA "

Namely, could someone explain what is the actual “approximation”? Is it QQTA or just QQT or just Q? The video mentions how QQT should approximate the identity at least as it acts on A - how is QQT different from an identify (presumably it would have lesser column/row rank since its the product of lower rank matrices, but is there something else I should know about it?)

  1. Finding Q: In the process of generating the image of Q we choose random vectors w_i -> could we have instead chosen w_i to be the identity matrix of whatever size we wanted? Isn’t this orthogonal like we ultimately want, and its garaunteed to span its dimension? Is there something special about using a random matrix W? My initial thoughts here are that if you pick a truncate dimension less than the second dimension of A, then you will be missing out on that many columns, but I don’t understand entirely why a random combination will be good enough.

Thanks for the great materials!