@article{ipsen_wentworth_2014, title={THE EFFECT OF COHERENCE ON SAMPLING FROM MATRICES WITH ORTHONORMAL COLUMNS, AND PRECONDITIONED LEAST SQUARES PROBLEMS}, volume={35}, ISSN={["1095-7162"]}, url={http://www.scopus.com/inward/record.url?eid=2-s2.0-84919934241&partnerID=MN8TOARS}, DOI={10.1137/120870748}, abstractNote={Motivated by the least squares solver Blendenpik, we investigate three strategies for uniform sampling of rows from $m\times 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 $\mathcal{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...}, number={4}, journal={SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS}, author={Ipsen, Ilse C. F. and Wentworth, Thomas}, year={2014}, pages={1490–1520} }