Randomized strong-rank revealing QR factorization

We consider a randomized strong rank-revealing QR factorization and show that it effectively reveals the spectral properties of a matrix M.  This factorization, already known in the literature and related to the sketch and precondition approach, can be used to address problems such as selecting a subset of the columns of M, computing its low-rank approximation, estimating its rank, or approximating its null space.  Given a random sketching matrix S that satisfies the eps-subspace embedding property for range(M), we show that the strong rank revealing QR factorization of B=SM allows to select columns that capture the spectrum of M with strong rank-revealing guarantees, making it particularly effective for approximating its singular values. We further discuss an efficient approach for computing the strong rank-revealing QR factorization of B through an additional sketch that relies on a sparse subspace embedding.  The resulting bounds exhibit a reduced dependence on the number of columns of B compared to those obtained from the strong rank-revealing QR factorization of B. Moreover, when the leverage scores are known, such as for orthogonal matrices, or can be efficiently approximated, the bounds become entirely independent of the column dimension.