  In this work, we analyze a sublinear-time algorithm for selecting a few rows
and columns of a matrix for low-rank approximation purposes. The algorithm is
based on an initial uniformly random selection of rows and columns, followed by
a refinement of this choice using a strong rank-revealing QR factorization. We
prove bounds on the error of the corresponding low-rank approximation (more
precisely, the CUR approximation error) when the matrix is a perturbation of a
low-rank matrix that can be factorized into the product of matrices with
suitable incoherence and/or sparsity assumptions.
