How to reveal the rank of a matrix?
<|reference_start|>How to reveal the rank of a matrix?: We study algorithms called rank-revealers that reveal a matrix's rank structure. Such algorithms form a fundamental component in matrix compression, singular value estimation, and column subset selection problems. While column-pivoted QR has been widely adopted due to its practicality, it is not always a rank-revealer. Conversely, Gaussian elimination (GE) with a pivoting strategy known as global maximum volume pivoting is guaranteed to estimate a matrix's singular values but its exponential complexity limits its interest to theory. We show that the concept of local maximum volume pivoting is a crucial and practical pivoting strategy for rank-revealers based on GE and QR. In particular, we prove that it is both necessary and sufficient; highlighting that all local solutions are nearly as good as the global one. This insight elevates Gu and Eisenstat's rank-revealing QR as an archetypal rank-revealer, and we implement a version that is observed to be at most $2\times$ more computationally expensive than CPQR. We unify the landscape of rank-revealers by considering GE and QR together and prove that the success of any pivoting strategy can be assessed by benchmarking it against a local maximum volume pivot.<|reference_end|>
@article{damle2024how,
    title={How to reveal the rank of a matrix?},
    author={Anil Damle, Silke Glas, Alex Townsend, Annan Yu},
    journal={arXiv preprint arXiv:2405.04330},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.04330},
    primaryClass={math.NA cs.NA}
}