Sketching for Linear Algebra III: Randomized Hadamard, Kernel Methods

on YouTube ↗01h 04m

" summary

Describes how to compute leverage scores via sketching by forming S A, QR on the sketch, forming R^{-1}, multiplying by a short JL matrix pi of size M' = O(log n / ε^2), and estimating row norms to get leverage estimates that yield sampling with about D/ε^2 samples and subspace embeddings. Claims SRHT (a Hadamard + sign flip + subsampling pipeline) makes leverage scores nearly uniform via Ledoux concentration so uniform sampling works. Reports time roughly NNZ(A)·O(ε^{-2} log n) plus poly(D,1/ε), and notes extensions: random Fourier features, TensorSketch, FastFood.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 0:59Uniform Sampling
3. 1:23Length Squared Sampling
4. 2:45Leverage Score Sampling
5. 42:43Running Time
6. 49:30Subsampled Randomized Hadamard Transform

" related talks

• 01h 04mSketching and Randomized Linear AlgebraDavid P. Woodruff · Sublinear Algorithms Boot Camp 2024
• 01h 03mSketching as a Tool for Numerical Linear AlgebraDavid P. Woodruff · Fast Algorithms via Spectral Methods 2014
• 01h 27mPast, Present and Future of Randomized Numerical Linear Algebra IMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 32mRandomized Numerical Linear Algebra: OverviewPetros Drineas · Randomized Numerical Linear Algebra and Applications 2018
• 48mRandomized Numerical Linear AlgebraPetros Drineas · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 33mRandomized Least Squares Optimization and its Incredible Utility for Large-Scale Tensor Decomp...Tamara Kolda · Extroverted Sublinear Algorithms 2024
• 31mSimple and Deterministic Matrix SketchesEdo Liberty · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 28mSketching for M-Estimators: A Unified Approach to Robust RegressionDavid P. Woodruff · Information Theory, Learning and Big Data (Simons Institute, 2015)