Fast randomized numerical rank estimation for numerically low-rank matrices

DOI10.1016/j.laa.2024.01.001arXiv2105.07388OpenAlexW4390661931MaRDI QIDQ6154411

Yuji Nakatsukasa, Maike Meier

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)

Cites Work

• Unnamed Item
• Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions
• A well-conditioned estimator for large-dimensional covariance matrices
• Nonlinear shrinkage estimation of large-dimensional covariance matrices
• Concentration inequalities and moment bounds for sample covariance operators
• Spectrum estimation for large dimensional covariance matrices using random matrix theory
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• Statistical eigen-inference from large Wishart matrices
• Spectral analysis of large dimensional random matrices
• On the distribution of the largest eigenvalue in principal components analysis
• Analytical nonlinear shrinkage of large-dimensional covariance matrices
• Exact matrix completion via convex optimization
• Approximating Spectral Densities of Large Matrices
• Improved Matrix Algorithms via the Subsampled Randomized Hadamard Transform
• LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems
• Computational Advertising: Techniques for Targeting Relevant Ads
• Efficient estimation of eigenvalue counts in an interval
• A fast randomized algorithm for overdetermined linear least-squares regression
• Non-asymptotic theory of random matrices: extreme singular values
• IMPROVED ANALYSIS OF THE SUBSAMPLED RANDOMIZED HADAMARD TRANSFORM
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Low-Rank Approximation and Regression in Input Sparsity Time
• Sparser Johnson-Lindenstrauss Transforms
• Two Theorems on Singular Values and Eigenvalues
• Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
• Efficient Randomized Algorithms for the Fixed-Precision Low-Rank Matrix Approximation
• On the Singular Values of Matrices with Displacement Structure
• High-Dimensional Statistics
• High-Dimensional Probability
• Why Are Big Data Matrices Approximately Low Rank?
• Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
• Streaming Low-Rank Matrix Approximation with an Application to Scientific Simulation
• randUTV
• The Effect of Coherence on Sampling from Matrices with Orthonormal Columns, and Preconditioned Least Squares Problems
• Alice and Bob Meet Banach
• Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
• Fast matrix rank algorithms and applications
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES
• Eigenvalues of a matrix in the streaming model
• Randomized numerical linear algebra: Foundations and algorithms

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