Randomized Algorithms for Computing Full Matrix Factorizations
summary
Randomized projections produce a blocked UTV-style factorization that reveals rank while spending almost all work in matrix–matrix multiplies; a single pass plus two cheap power iterations typically drives off-diagonal blocks to 1e-2–1e-5 and makes diagonal entries match singular values closely. Block size is a tuning parameter (100–1000), runs out‑of‑core to 100k×100k, and on 14 cores shows roughly 5× speedup versus MKL column‑pivoted QR; multi‑core code is available and GPU/distributed ports are in progress. UTV/RandUTV uses randomized projections.
AI-written summary · about
chapters (8)
- 0:00Start
- 2:49Randomized Svd
- 15:56Blocked Algorithm
- 21:41Relative Errors
- 24:34Computational Timings
- 27:15Gpu Implementation
- 28:37Column Pivoting
- 32:31References
related talks
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
48mRandomized Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
19mEfficient Decentralized Federated Singular Vector Decomposition
43mThe Linear Algebra of Deep Learning