SMOOTHED ANALYSIS OF SYMMETRIC RANDOM MATRICES WITH CONTINUOUS DISTRIBUTIONS

We study invertibility of matrices of the form $D+R$ where $D$ is anarbitrary symmetric deterministic matrix, and $R$ is a symmetric random matrixwhose independent entries have continuous distributions with bounded densities.We show that $|(D+R)^{-1}| = O(n^2)$ with high probability. The bound iscompletely independent of $D$. No moment assumptions are placed on $R$; inparticular the entries of $R$ can be arbitrarily heavy-tailed.