Krylov Methods are (nearly) Optimal for Low-Rank Approximation.

Ainesh Bakshi, Shyam Narayanan

Browse the full FOCS paper archive.