Sketching and Projecting
summary
Shows that sketch-and-project solvers — e.g. randomized Kaczmarz, block Kaczmarz and Gaussian sketch updates — give exponential convergence to a small error horizon that scales with noise, sketch size and conditioning; introduces QuantileRK and QuantileSGD to detect and ignore sparse, arbitrarily large corruptions (empirically tolerating ~20% spikes; theory tolerates β < 0.5), proves convergence rates for sketched LDA predictions, and reports few-iteration accuracy matching full solves.
AI-written summary · about
chapters (9)
- 0:00Sketching and projecting methods
- 1:04Randomized projection methods
- 3:00Kaczmarz method
- 7:29Sketch and project framework
- 15:16Noisy vs corrupted systems
- 22:30QuantileRK for corruption
- 32:05QuantileRK algorithm
- 42:07Sketching for Linear Discriminant Analysis
- 46:49Summary
related talks
01h 03mSketching as a Tool for Numerical Linear Algebra
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
01h 04mSketching and Randomized Linear Algebra
28mRandomized Constrained Matrix Decompositions
01h 04mSketching for Linear Algebra III: Randomized Hadamard, Kernel Methods
33mRobust Sketching for Large-Scale Multi-Instance Conic Optimization
01h 01mRobustness, Stochastics, Uncertainty 2
01h 10mSketching for Linear Algebra: Basics of Dimensionality Reduction and CountSketch II