Gaussian Regularization of the Pseudospectrum and Numerical Linear Algebra
summary
Shows that adding a small complex Gaussian regularizes nonnormal spectra: a Toeplitz example has Toeplitz n=100: κ≈10^30 but a tiny random perturbation yields perturbation 10^-5 → κ≈10^5. Proves existence result κ_E ≤ 4 n^{3/2}/δ so every A has a δ perturbation with polynomial conditioning, and a probabilistic bound on eigenvalue sensitivity giving expected sum of squared κλ ≤ n/γ^2 times area. Delivers a randomized algorithm near matrix-multiplication time that diagonalizes well after perturbation.
AI-written summary · about
chapters (11)
- 0:00Start
- 14:20Condition Number of Eigenvalues
- 19:50Probabilistic Analysis of ki
- 27:13E-pseudospectrum
- 29:35Pseudospectra of Examples, e = 10-1...
- 32:53Area of the pseudospectrum Lemma 1: If M has distinct eigenvalues then for every open B
- 35:55Real Anticoncentration Theorem Sankar-Spielman-Teng'06 : For any real n x n matrix M, and G with i.i.d. real N(0,1) entries
- 39:54Expected Area of the Pseudospectrum Lemma 2. For any complex n x n matrix M, complex Gaussian G
- 41:52Expected Limiting Area of the Pseudospect Define the function
- 43:10Phenomenon behind the result
- 44:27Real Perturbations?