Reviews: Leveraged volume sampling for linear regression

This paper studies deficiencies of volume sampling, and proposes a modification based on leverage scores, or renormalizing the current ellipse before performing volumne rejection sampling. It improves the number of unbiased samples required to guarantee 1\pm\epsilon accuracy by a factor of \epsilon {-1}, and also demonstrates the good empirical performances of its routines on datasets from LibSVM (in Supplementary materials E). Both linear regression and volume sampling are well studied topics, and the observations made in this paper are quite surprising. The paper clearly outlines a class of matrices that are problematic for volume sampling, and then proves the properties of the revised methods. The proposed methods also exhibit significant empirical gains over other methods in the small sample size regime, which are arguable the more important cases. I believe these contributions are of significant interest to the study of both randomized sampling and randomized numerical linear algebra.