Instance Optimal Iterative Methods for Matrix Function Approximation

on YouTube ↗32m

" summary

Claim: Lanczos (Krylov) is instance-optimal for rational functions—for a degree-M/Q rational f with poles outside the spectrum, Lanczos output is within a provable factor of the best Krylov-subspace approximation, provided k > max(M, Q−1) and compared to degree k−Q+1 approximants. Tools: extend CG/Lanczos projection tricks, tridiagonal T eigendecomposition, and polynomial-to-rational reductions. Concrete bound: approximation factor scales like Q times the product of condition numbers of the shifted matrices (currently exponential in Q), while experiments show only about √(Q·κ) degradation; bound already beats uniform spectral-range guarantees.

AI-written summary · about

" chapters (15)

1. 0:00Matrix function approximation
2. 1:48Applications of matrix functions
3. 3:37Krylov subspace methods
4. 5:48Lanczos method
5. 8:38Lanczos for polynomials
6. 13:13Error bound for Lanczos
7. 15:40Limitations of error bounds
8. 18:29Instance optimality goal
9. 20:36Rational function results
10. 23:31Rational functions importance
11. 24:55Improving Lanczos error bounds
12. 26:20Proof sketch for inverse
13. 28:29Generalizing to 1/x²
14. 30:58Open questions
15. 32:02Conclusion & Q&A