Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2405.04330 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929370908590080 |
|---|---|
| author | Damle, Anil Glas, Silke Townsend, Alex Yu, Annan |
| author_facet | Damle, Anil Glas, Silke Townsend, Alex Yu, Annan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04330 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | How to reveal the rank of a matrix? Damle, Anil Glas, Silke Townsend, Alex Yu, Annan Numerical Analysis 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. |
| title | How to reveal the rank of a matrix? |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2405.04330 |