Near-Optimal Entrywise Sampling for Data Matrices

Dimitris Achlioptas, Zohar Karnin, Edo Liberty

We consider the problem of selecting non-zero entries of a matrix $A$ in order to produce a sparse sketch of it, $B$, that minimizes $\Vert A-B{\Vert }_2$. For large $m\times n$ matrices, s…