Faster Spectral Algorithms via Approximation Theory

on YouTube ↗01h 03m

" summary

Uniform polynomial approximations turn matrix powers into O(M · D) work and give X^S approximants of degree about sqrt(S)·log(1/δ), so S-step walks and power-method–style tasks run in roughly M·√S time for δ-error. Chebyshev machinery and a Chernoff tail control this; Markov-type lower bounds show the √S barrier. For e^{-x} a rational 1/p(x) with degree O(log(1/δ)) approximates on [0,∞) and, combined with Laplacian solvers, Euler–Maclaurin discretization and Lanczos yields matrix-exponential times vector in near-linear or polylog dependence on the norm.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:34The Goal
3. 3:48Approximation Theory
4. 8:42Algorithms/Numerical Linear Alg.- f(A)v. Eigenvalues
5. 15:04Example: Approximating the Monomial
6. 18:05Chebyshev Polynomials The Chebyshev polynomial of deg d is defined recursively to be
7. 20:22Back to Approximating Monomials
8. 31:47Lower Bounds for Polynomial Approximations
9. 34:07Example: Approximating the Exponential
10. 38:02Why any Rational Approximation is not Enough?
11. 40:34Rational Approximation with Negative Poles
12. 43:21Computing the Matrix Exponential- Summary
13. 46:29Matrix Inversion via Exponentiation
14. 52:22A Heuristic for solving PSD Systems?