Fast randomized numerical rank estimation for numerically low-rank matrices

DOI10.1016/J.LAA.2024.01.001arXiv2105.07388OpenAlexW4390661931MaRDI QIDQ6154411FDOQ6154411

Authors: Maike Meier, Yuji Nakatsukasa 

Publication date: 15 February 2024

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

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 previous studies. In this work we develop a randomized algorithm for estimating the numerical rank of a 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. The rank can hence be taken to be the number of singular values of the sketch that are larger than the prescribed threshold. For an $mimesn$ $(mgeqn)$ matrix of numerical rank $r$, the algorithm runs with complexity $O(mnlogn+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.

Full work available at URL: https://arxiv.org/abs/2105.07388

zbMATH Keywords

randomized algorithmrank estimationnumerical rankMarčenko-Pastur rule

Mathematics Subject Classification ID

Randomized algorithms (68W20) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• randUTV: a blocked randomized algorithm for computing a rank-revealing UTV factorization
• Spectral analysis of large dimensional random matrices
• A well-conditioned estimator for large-dimensional covariance matrices
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• On the distribution of the largest eigenvalue in principal components analysis
• Improved matrix algorithms via the subsampled randomized Hadamard transform
• High-dimensional statistics. A non-asymptotic viewpoint
• High-dimensional probability. An introduction with applications in data science
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Exact matrix completion via convex optimization
• Local operator theory, random matrices and Banach spaces.
• Spectrum estimation for large dimensional covariance matrices using random matrix theory
• Low-Rank Approximation and Regression in Input Sparsity Time
• Why Are Big Data Matrices Approximately Low Rank?
• The effect of coherence on sampling from matrices with orthonormal columns, and preconditioned least squares problems
• Improved analysis of the subsampled randomized Hadamard transform
• Non-asymptotic theory of random matrices: extreme singular values
• Fast matrix rank algorithms and applications
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Statistical eigen-inference from large Wishart matrices
• A fast randomized algorithm for overdetermined linear least-squares regression
• Randomized numerical linear algebra: Foundations and algorithms
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Sparser Johnson-Lindenstrauss transforms
• Eigenvalues of a matrix in the streaming model
• Concentration inequalities and moment bounds for sample covariance operators
• Approximating spectral densities of large matrices
• Two Theorems on Singular Values and Eigenvalues
• Streaming low-rank matrix approximation with an application to scientific simulation
• Alice and Bob Meet Banach
• Analytical nonlinear shrinkage of large-dimensional covariance matrices
• Sketching as a tool for numerical linear algebra
• LSRN: A parallel iterative solver for strongly over- or underdetermined systems
• Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
• Efficient estimation of eigenvalue counts in an interval.
• On the singular values of matrices with displacement structure
• Nearly tight oblivious subspace embeddings by trace inequalities
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities

Cited In (2)

• A subspace constrained randomized Kaczmarz method for structure or external knowledge exploitation
• A sequential multilinear Nyström algorithm for streaming low-rank approximation of tensors in Tucker format

This page was built for publication: Fast randomized numerical rank estimation for numerically low-rank matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154411)