Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
read the original abstract
Randomized numerical linear algebra - RandNLA, for short - concerns the use of randomization as a resource to develop improved algorithms for large-scale linear algebra computations. The origins of contemporary RandNLA lay in theoretical computer science, where it blossomed from a simple idea: randomization provides an avenue for computing approximate solutions to linear algebra problems more efficiently than deterministic algorithms. This idea proved fruitful in the development of scalable algorithms for machine learning and statistical data analysis applications. However, RandNLA's true potential only came into focus upon integration with the fields of numerical analysis and "classical" numerical linear algebra. Through the efforts of many individuals, randomized algorithms have been developed that provide full control over the accuracy of their solutions and that can be every bit as reliable as algorithms that might be found in libraries such as LAPACK. Recent years have even seen the incorporation of certain RandNLA methods into MATLAB, the NAG Library, NVIDIA's cuSOLVER, and SciKit-Learn. For all its success, we believe that RandNLA has yet to realize its full potential. In particular, we believe the scientific community stands to benefit significantly from suitably defined "RandBLAS" and "RandLAPACK" libraries, to serve as standards conceptually analogous to BLAS and LAPACK. This 200-page monograph represents a step toward defining such standards. In it, we cover topics spanning basic sketching, least squares and optimization, low-rank approximation, full matrix decompositions, leverage score sampling, and sketching data with tensor product structures (among others). Much of the provided pseudo-code has been tested via publicly available MATLAB and Python implementations.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
PEPSKit.jl: A Julia package for projected entangled-pair state simulations
PEPSKit.jl is a new Julia software package providing high-level algorithms for iPEPS tensor-network simulations of 2D quantum systems with symmetry support.
-
Sharp analysis of sketched least squares and randomized low-rank approximation
Random orthonormal matrices are minimax optimal for sketched least squares and rotation-invariant embeddings for randomized SVD, yielding the sharpest error bounds.
-
Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation
Accelerates the power method for extracting top principal components using fast sketching and regularized spectral approximation for stronger low-rank guarantees.
-
Randomized Sketching is Robust to Low-Precision Rounding on GPUs
FP16 SparseStack on GPUs shows embedding quality insensitive to rounding method, with sketch distribution as the primary accuracy driver across tested inputs.
-
A multilevel sketch-and-solve method for overdetermined least squares problems
A multilevel sketch-and-solve estimator reduces variance faster than averaging independent sketches but incurs slightly higher computational cost, making the approach unattractive for least squares problems.
-
Approximate Distributed Coded Computing: Polynomial Codes and Randomized Sketching
Combines polynomial codes and randomized sketching into approximate distributed schemes that mitigate stragglers during optimization and machine learning tasks.
-
Randomized batch-sampling Kaczmarz methods for solving linear systems
A unified randomized batch-sampling Kaczmarz framework yields scale-invariant expected linear convergence bounds for block methods solving linear systems.
-
Stabilizing randomized GMRES through flexible GMRES
Flexible GMRES stabilizes sketched GMRES through a new residual bound, producing a practical randomized solver with minimal tuning and robust non-increasing residual norms.
-
Randomized coupled decompositions
Direct SVD solves coupled decompositions; randomized versions with novel balanced subspace selection improve efficiency and apply to face recognition.
-
PEPSKit.jl: A Julia package for projected entangled-pair state simulations
PEPSKit.jl is a Julia package that supplies high-level algorithms for ground-state, time-evolution and finite-temperature iPEPS simulations with symmetry support on various lattices.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.