  In this paper, we consider the problem of column subset selection. We present
a novel analysis of the spectral norm reconstruction for a simple randomized
algorithm and establish a new bound that depends explicitly on the sampling
probabilities. The sampling dependent error bound (i) allows us to better
understand the tradeoff in the reconstruction error due to sampling
probabilities, (ii) exhibits more insights than existing error bounds that
exploit specific probability distributions, and (iii) implies better sampling
distributions. In particular, we show that a sampling distribution with
probabilities proportional to the square root of the statistical leverage
scores is always better than uniform sampling and is better than leverage-based
sampling when the statistical leverage scores are very nonuniform. And by
solving a constrained optimization problem related to the error bound with an
efficient bisection search we are able to achieve better performance than using
either the leverage-based distribution or that proportional to the square root
of the statistical leverage scores. Numerical simulations demonstrate the
benefits of the new sampling distributions for low-rank matrix approximation
and least square approximation compared to state-of-the art algorithms.
