Fast randomized numerical rank estimation for numerically low-rank matrices.
In: Linear Algebra & its Applications, Jg. 686 (2024-04-01), S. 1-32
Online
academicJournal
Matrices with low-rank structure are ubiquitous in scientific computing. Choosing an appropriate rank is a key step in many computational algorithms that exploit low-rank structure. However, estimating the rank has been done largely in an ad-hoc fashion in large-scale settings. In this work we develop a randomized algorithm for estimating the numerical rank of a (numerically low-rank) matrix. The algorithm is based on sketching the matrix with random matrices from both left and right; the key fact is that with high probability, the sketches preserve the orders of magnitude of the leading singular values. We prove a result on the accuracy of the sketched singular values and show that gaps in the spectrum are detected. For an m × n (m ≥ n) matrix of numerical rank r , the algorithm runs with complexity O (m n log n + r 3) , or less for structured matrices. The steps in the algorithm are required as a part of many low-rank algorithms, so the additional work required to estimate the rank can be even smaller in practice. Numerical experiments illustrate the speed and robustness of our rank estimator. [ABSTRACT FROM AUTHOR]
Titel: |
Fast randomized numerical rank estimation for numerically low-rank matrices.
|
---|---|
Autor/in / Beteiligte Person: | Meier, Maike ; Nakatsukasa, Yuji |
Link: | |
Zeitschrift: | Linear Algebra & its Applications, Jg. 686 (2024-04-01), S. 1-32 |
Veröffentlichung: | 2024 |
Medientyp: | academicJournal |
ISSN: | 0024-3795 (print) |
DOI: | 10.1016/j.laa.2024.01.001 |
Schlagwort: |
|
Sonstiges: |
|