Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices

Hussam Al Daas, Grey Ballard, Laura Grigori +4

Sketching is widely used in randomized linear algebra for low-rank matrix approximation, column subset selection, and many other problems, and it has gained significant traction in…