Fast randomized numerical rank estimation for numerically low-rank matrices

DOI10.1016/J.LAA.2024.01.001MaRDI QIDQ6154411OpenAlexFDO

Authors Maike Meier, Yuji Nakatsukasa

Publication date 15 February 2024

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

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)

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.

Recommendations

• A fast randomized algorithm for the approximation of matrices
• Randomized algorithms for the low-rank approximation of matrices
• Fast monte-carlo algorithms for finding low-rank approximations
• Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix
• Practical sketching algorithms for low-rank matrix approximation

Cites work

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

Cited in

(3)

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

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)