  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. We also show that
under the assumption of power-law decay of ridge leverage scores, this
deterministic algorithm is provably as accurate as randomized algorithms.
  Lastly, ridge regression is frequently used to regularize ill-posed linear
least-squares problems. While ridge regression provides shrinkage for the
regression coefficients, many of the coefficients remain small but non-zero.
Performing ridge regression with the matrix sketch returned by our algorithm
and a particular regularization parameter forces coefficients to zero and has a
provable (1 + {\epsilon}) bound on the statistical risk. As such, it is an
interesting alternative to elastic net regularization.
