2025/09/03 by Israa Fakih, Laura Grigori, Fakih, Israa +1 · 1 citation
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #Face and Expression Recognition
paper · pdf · doi:10.48550/arxiv.2509.03198
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 ΩT, where Ω is a sparse oblivious subspace embedding for a subspace of dimension rank(A). The sparsity structure of Ω 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).