Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner by having no failure probability and always returning the same results. We provide provable guarantees for deterministic column sampling using ridge leverage scores. The matrix sketch returned by our algorithm is a column subset of the original matrix, yielding additional interpretability. Like the randomized counterparts, the deterministic algorithm provides $(1+\epsilon)$ error column subset selection, $(1+\epsilon)$ error projection-cost preservation, and an additive-multiplicative spectral bound.

I also strongly approve of the suggestion of highlighting more the experimental results in the main paper. RLSs are well known quantities used in randomized sketching and coreset selection to identify influential samples. Similarly, it is known that sampling **and reweighting** rows of a matrix A according to their RLS produces a sketch that whp approximates the true matrix up to a small multiplicative and additive error. The authors prove that sorting the rows in descending order (by RLS), and deterministically selecting them until the RLS falls under a carefully chosen threshold is also sufficient to obtain a provably accurate sketch. Therefore, they propose deterministic RLS selection as a convenient and provably accurate rule for column selection, with improved interpretability over optimization based alternative such as lasso and elastic net.

Ridge leverage scores provide a balance between low-rank approximation and regularization, and are ubiquitous in randomized linear algebra and machine learning. Deterministic algorithms are also of interest in the moderately big data regime, because deterministic algorithms provide interpretability to the practitioner by having no failure probability and always returning the same results. We provide provable guarantees for deterministic column sampling using ridge leverage scores. The matrix sketch returned by our algorithm is a column subset of the original matrix, yielding additional interpretability. Like the randomized counterparts, the deterministic algorithm provides $(1 \epsilon)$ error column subset selection, $(1 \epsilon)$ error projection-cost preservation, and an additive-multiplicative spectral bound.