Gaussian Regularization of the Pseudospectrum and Davies' Conjecture

2019/06/27 by Banks, Jess, Kulkarni, Archit, Mukherjee, Satyaki +1 · 1 citation
#FOS: Mathematics #Functional Analysis (math.FA) #Numerical Analysis (math.NA) #Probability (math.PR) #Spectral Theory (math.SP)

paper · doi:10.48550/arxiv.1906.11819

Abstract

A matrix A∈ℂ^{n× n} is diagonalizable if it has a basis of linearly independent eigenvectors. Since the set of nondiagonalizable matrices has measure zero, every A∈ ℂ^{n× n} is the limit of diagonalizable matrices. We prove a quantitative version of this fact conjectured by E.B. Davies: for each δ∈ (0,1), every matrix A∈ ℂ^{n× n} is at least δ‖A‖-close to one whose eigenvectors have condition number at worst c_n/δ, for some constants c_n dependent only on n. Our proof uses tools from random matrix theory to show that the pseudospectrum of A can be regularized with the addition of a complex Gaussian perturbation. Along the way, we explain how a variant of a theorem of Śniady implies a conjecture of Sankar, Spielman and Teng on the optimal constant for smoothed analysis of condition numbers.

Cited by

• Structured Divide-and-Conquer for the Definite Generalized Eigenvalue Problem

Related

• On the real Davies' conjecture
• Regularization of non-normal matrices by Gaussian noise - the banded\n Toeplitz and twisted Toeplitz cases
• Sparse Pseudospectral Shattering
• Convergence of the spectral measure of non normal matrices
• Pseudospectral Shattering, the Sign Function, and Diagonalization in Nearly Matrix Multiplication Time