Adaptive, Matrix-Free Low-Rank Approximation

DOI10.48550/arXiv.2607.06758MaRDI QIDQ7283906arXivFDO

Authors Arnel I. Smith, Elly Do, Chao Chen

Publication date 7 July 2026

Published in arXiv

Tldr We develop adaptive matrix-free low-rank approximation algorithms that can accurately determine rank adaptively and are suitable for large-scale applications. Our randomized error indicator estimates residual norms from a random sketch down to machine precision, and our rank-pruning step decouples block size from final rank using BLAS-3-friendly blocks.

Full work available at URL https://doi.org/10.48550/arXiv.2607.06758

arXiv classification

math.NA

Cites work

• A computational framework for infinite-dimensional Bayesian inverse problems. I: The linearized case, with application to global seismic inversion
• A general error analysis for randomized low-rank approximation with application to data assimilation
• A Multilinear Singular Value Decomposition
• A novel adaptive low-rank matrix approximation method for image compression and reconstruction
• A randomized blocked algorithm for efficiently computing rank-revealing factorizations of matrices
• A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines
• Adaptive Parallelizable Algorithms for Interpolative Decompositions via Partially Pivoted LU
• Approximation of boundary element matrices
• Compressing Rank-Structured Matrices via Randomized Sampling
• Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation
• Efficient algorithms for computing rank‐revealing factorizations on a GPU
• Efficient randomized algorithms for the fixed-precision low-rank matrix approximation
• Fast algorithms for Bayesian uncertainty quantification in large-scale linear inverse problems based on low-rank partial Hessian approximations
• Fast and stable randomized low-rank matrix approximation
• Fast construction of hierarchical matrix representation from matrix-vector multiplication
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Fast Rank Adaptive CUR via a Recycled Small Sketch
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Hierarchical matrices: algorithms and analysis
• Householder QR factorization with randomization for column pivoting (HQRRP)
• Improved bounds for small-sample estimation
• Linear-Complexity Black-Box Randomized Compression of Rank-Structured Matrices
• Matrix Computations
• Numerical methods for large eigenvalue problems
• On the Compression of Low Rank Matrices
• On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Randomised methods for dynamical low-rank approximation
• Randomized Algorithms for Low-Rank Matrix and Tensor Decompositions
• Randomized Numerical Linear Algebra: Foundations & Algorithms
• Randomized QR with column pivoting
• Randomized sparse direct solvers
• Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
• Randomly pivoted Cholesky: practical approximation of a kernel matrix with few entry evaluations
• Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
• Robust Blockwise Random Pivoting: Fast and Accurate Adaptive Interpolative Decomposition
• Subspace Iteration Randomization and Singular Value Problems

Cited in

(1)

• Hutch#: Optimal non-adaptive Frobenius norm estimation

This page was built for publication: Adaptive, Matrix-Free Low-Rank Approximation

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