Revisiting Approximate Leverage Score Sketching for Matrix Least Squares

Abstract

We revisit the problem of sketching using approximate leverage scores for matrix least squares problems of the form $\Vert AX-B{\Vert }_F^2$ where the design matrix $A\in {\mathbb{R}}^{N\times r}$ is tall and skinny with $N\gg r$. We derive the theoretical results from first principles and clarify the relation to previously stated bounds, improving some constants along the way. One can characterize the utility of a sketching scheme according to the number of samples it needs for an $\epsilon$-accurate solution with high probability. Assuming $\epsilon$ is suitably small, we will show that approximate leverage score sampling requires $4r/({\hat{I}}^2\hat{I}´\epsilon )$ samples, where $\hat{I}´$ is the failure probability and ${\hat{I}}^2\in (0,1]$ is a measure of the quality of the approximate leverage scores such that ${\hat{I}}^2=1$ corresponds to using exact leverage scores. In cases where a few approximate leverage scores are very large (summing to $p_{\det }$), we also show that using a hybrid deterministic and random sampling scheme reduces the required number of samples by a factor of $1/(1-p_{\det })$.

This is detailed and standalone derivation of a result that already appears in (arXiv:2006.16438, Appendix A). arXiv admin note: substantial text overlap with arXiv:2006.16438