A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations
<|reference_start|>A sublinear-time randomized algorithm for column and row subset selection based on strong rank-revealing QR factorizations: 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.<|reference_end|>
@article{cortinovis2024a,
    title={A sublinear-time randomized algorithm for column and row subset
  selection based on strong rank-revealing QR factorizations},
    author={Alice Cortinovis and Lexing Ying},
    journal={arXiv preprint arXiv:2402.13975},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13975},
    primaryClass={math.NA cs.NA}
}