  Motivated by the least squares solver Blendenpik, we investigate three
strategies for uniform sampling of rows from m x n matrices Q with orthonormal
columns. The goal is to determine, with high probability, how many rows are
required so that the sampled matrices have full rank and are well-conditioned
with respect to inversion.
  Extensive numerical experiments illustrate that the three sampling strategies
(without replacement, with replacement, and Bernoulli sampling) behave almost
identically, for small to moderate amounts of sampling. In particular, sampled
matrices of full rank tend to have two-norm condition numbers of at most 10.
  We derive a bound on the condition number of the sampled matrices in terms of
the coherence {\mu} of Q. This bound applies to all three different sampling
strategies; it implies a, not necessarily tight, lower bound of O(m {\mu}
ln(n)) for the number of sampled rows; and it is realistic and informative even
for matrices of small dimension and the stringent requirement of a 99 percent
success probability.
  For uniform sampling with replacement we derive a potentially tighter
condition number bound in terms of the leverage scores of Q. To obtain a more
easily computable version of this bound, in terms of just the largest leverage
scores, we first derive a general bound on the two-norm of diagonally scaled
matrices.
  To facilitate the numerical experiments and test the tightness of the bounds,
we present algorithms to generate matrices with user-specified coherence and
leverage scores. These algorithms, the three sampling strategies, and a large
variety of condition number bounds are implemented in the Matlab toolbox
kappa_SQ_v3.
