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 |F2 where the design matrix A ∈ ℝN × 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 β ∈ (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 prm 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-prm det).