REVIEW 8 cited by
Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
Forward citations
Cited by 8 Pith papers
-
Faster Linear Algebra Algorithms with Structured Random Matrices
Randomized sketching needs only the new OSI property, not the full subspace embedding, and multiple structured matrices satisfy it with near-optimal cost.
-
Linear-Scaling Tensor Train Sketching
TTStack achieves oblivious subspace embedding and injection for tensor trains with sample complexity linear in order d and subspace dimension r, yielding quasi-optimal randomized TT rounding.
-
The matrix-vector complexity of $Ax=b$
Randomized matrix-vector algorithms need Ω(κ log(1/ε)) products for general linear systems (two-sided) and n products without the transpose, matching CGNE and GMRES.
-
Sketch low-rank dynamics: orthogonal vs. oblique projections
Orthogonal sketch DLRA preserves classical DLRA dynamics and stability; oblique sketching of the Galerkin condition fails on large perpendicular residuals such as Vlasov–Poisson.
-
Sequential Preconditioned Conjugate Gradient Method for Linear Statistical Models
A two-stage randomized solver that warms up PCG on a sequence of larger sketched least-squares problems reaches OLS-level prediction accuracy with fewer full-data iterations than IDS or plain PCG.
-
Hybrid least squares for learning functions from highly noisy data
A two-stage least-squares algorithm combining Christoffel sampling with experimental-design-based allocation of repeated evaluations improves sample complexity for learning noisy conditional expectations.
-
Anatomy of High-Performance Column-Pivoted QR Decomposition
A randomized, modular QR-with-column-pivoting framework (BQRRP) is shown to run up to two orders of magnitude faster than LAPACK's GEQP3 on AMD CPUs and near unpivoted-QR speed on an H100 GPU, in the authors' open-sou...
-
Spectral Estimation with Free Decompression
Free decompression evolves a small submatrix spectrum into an estimate of a large matrix spectrum using a PDE derived from free probability, the Nica-Speicher free compression theorem.
Discussion (0). Sign in to comment.