Revisiting Approximate Leverage Score Sketching for Matrix Least Squares

We revisit the problem of sketching using approximate leverage scores for matrix least squares problems of the form $\| AX - B \|_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 $\varepsilon$-accurate solution with high probability. Assuming $\varepsilon$ is suitably small, we will show that approximate leverage score sampling requires $4r/(βδ\varepsilon)$ samples, where $δ$ is the failure probability and $β\in (0,1]$ is a measure of the quality of the approximate leverage scores such that $β=1$ corresponds to using exact leverage scores. In cases where a few approximate leverage scores are very large (summing to $p_{\rm 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_{\rm det})$.