Randomized strong rank-revealing QR for column subset selection and low-rank matrix approximation

We discuss a randomized strong rank-revealing QR factorization that effectively reveals the spectrum of a matrix $\mathbf{\text{M}}$. This factorization can be used to address problems such as selecting a subset of the columns of $\mathbf{\text{M}}$, computing its low-rank approximation, estimating its rank, or approximating its null space. Given a random sketching matrix $\mathrm{\Omega }$ that satisfies the $\epsilon$-embedding property for a subspace within the range of $\mathbf{\text{M}}$, the factorization relies on selecting columns that allow to reveal the spectrum via a deterministic strong rank-revealing QR factorization of ${\mathbf{\text{M}}}^{sk}=\mathrm{\Omega }\mathbf{\text{M}}$, the sketch of $\mathbf{\text{M}}$. We show that this selection leads to a factorization with strong rank-revealing properties, making it suitable for approximating the singular values of $\mathbf{\text{M}}$.