Back to Search
Start Over
Fast randomized numerical rank estimation for numerically low-rank matrices.
- Source :
-
Linear Algebra & its Applications . Apr2024, Vol. 686, p1-32. 32p. - Publication Year :
- 2024
-
Abstract
- 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]
- Subjects :
- *LOW-rank matrices
*RANDOM matrices
*UBIQUITOUS computing
*SCIENTIFIC computing
Subjects
Details
- Language :
- English
- ISSN :
- 00243795
- Volume :
- 686
- Database :
- Academic Search Index
- Journal :
- Linear Algebra & its Applications
- Publication Type :
- Academic Journal
- Accession number :
- 175413307
- Full Text :
- https://doi.org/10.1016/j.laa.2024.01.001