Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings

In this paper, we introduce an efficient algorithm for column subset selection that combines the column-pivoted QR factorization with sparse subspace embeddings. The proposed method, SE-QRCS, is particularly effective for wide matrices with significantly more columns than rows. Starting from a matrix $A$, the algorithm selects $k$ columns from the sketched matrix $B = A \Omega^T$, where $\Omega$ is a sparse oblivious subspace embedding for a subspace of dimension $rank(A)$. The sparsity structure of $\Omega$ is then exploited to map the selected pivots back to the corresponding columns of $A$, which are then used to produce the final subset of selected columns. We prove that this procedure yields a factorization with strong rank-revealing properties, thus revealing the spectrum of $A$. The resulting bounds exhibit a reduced dependence on the number of columns of $A$ compared to those obtained from the strong rank-revealing QR factorization of $A$. For general matrices, the algorithm can be extended by first applying an additional subspace embedding of $range(A)$.