  Approximate solutions to large least squares problems can be computed
efficiently using leverage score-based row-sketches, but directly computing the
leverage scores, or sampling according to them with naive methods, still
requires an expensive manipulation and processing of the design matrix. In this
paper we develop efficient leverage score-based sampling methods for matrices
with certain Kronecker product-type structure; in particular we consider
matrices that are monotone lower column subsets of Kronecker product matrices.
Our discussion is general, encompassing least squares problems on infinite
domains, in which case matrices formally have infinitely many rows. We briefly
survey leverage score-based sampling guarantees from the numerical linear
algebra and approximation theory communities, and follow this with efficient
algorithms for sampling when the design matrix has Kronecker-type structure.
Our numerical examples confirm that sketches based on exact leverage score
sampling for our class of structured matrices achieve superior residual
compared to approximate leverage score sampling methods.
