Advanced Techniques for Low-Rank Matrix Approximation
summary
Presents spectral-revealing QR as a concrete alternative to rank-revealing QR, proves constant-factor bounds for truncated QR and flip-flop (QLP) improving tau^2 to tau^4, and shows block Lanczos (with block size B and Q iterations) achieves superlinear convergence in practice. Demonstrations include a 600×600 rank-60 image example, randomized QR with column pivoting matching scaled accuracy of truncated SVD, and a distributed implementation on 20k×20k and 50k×20k matrices that runs roughly an order of magnitude faster than ScaLAPACK column-pivoted QR.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:58Outline
- 1:50Acceptance Rates
- 2:19What is going on
- 2:55Traditional Approach
- 12:34Factorizations
- 15:47Rockman
- 16:29Method
- 19:57Comparison
- 26:45Quality vs Time
- 28:42Block Size
- 30:20Uniqueness
related talks
01h 27mPast, Present and Future of Randomized Numerical Linear Algebra I
01h 31mPast, Present and Future of Randomized Numerical Linear Algebra II
33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
48mRandomized Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II