Smoothed analysis of symmetric random matrices with continuous distributions

Farrell, Brendan; Vershynin, Roman

doi:10.1090/proc/12844

Smoothed analysis of symmetric random matrices with continuous distributions
HTML articles powered by AMS MathViewer

by Brendan Farrell and Roman Vershynin PDF

Proc. Amer. Math. Soc. 144 (2016), 2257-2261 Request permission

Abstract:

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

References

Alan Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. Matrix Anal. Appl. 9 (1988), no. 4, 543–560. MR 964668, DOI 10.1137/0609045
László Erdős, Benjamin Schlein, and Horng-Tzer Yau, Wegner estimate and level repulsion for Wigner random matrices, Int. Math. Res. Not. IMRN 3 (2010), 436–479. MR 2587574, DOI 10.1093/imrn/rnp136
Paul Alton Hagelstein, Weak $L^1$ norms of random sums, Proc. Amer. Math. Soc. 133 (2005), no. 8, 2327–2334. MR 2138875, DOI 10.1090/S0002-9939-05-07966-9
Hoi H. Nguyen, On the least singular value of random symmetric matrices, Electron. J. Probab. 17 (2012), no. 53, 19. MR 2955045, DOI 10.1214/EJP.v17-2165
Guangming Pan and Wang Zhou, Circular law, extreme singular values and potential theory, J. Multivariate Anal. 101 (2010), no. 3, 645–656. MR 2575411, DOI 10.1016/j.jmva.2009.08.005
Mark Rudelson and Roman Vershynin, The Littlewood-Offord problem and invertibility of random matrices, Adv. Math. 218 (2008), no. 2, 600–633. MR 2407948, DOI 10.1016/j.aim.2008.01.010
Mark Rudelson and Roman Vershynin, Invertibility of random matrices: unitary and orthogonal perturbations, J. Amer. Math. Soc. 27 (2014), no. 2, 293–338. MR 3164983, DOI 10.1090/S0894-0347-2013-00771-7
Mark Rudelson and Roman Vershynin, The least singular value of a random square matrix is $O(n^{-1/2})$, C. R. Math. Acad. Sci. Paris 346 (2008), no. 15-16, 893–896 (English, with English and French summaries). MR 2441928, DOI 10.1016/j.crma.2008.07.009
Daniel A. Spielman and Shang-Hua Teng, Smoothed analysis of algorithms, Proceedings of the International Congress of Mathematicians, Vol. I (Beijing, 2002) Higher Ed. Press, Beijing, 2002, pp. 597–606. MR 1989210
Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng, Smoothed analysis of the condition numbers and growth factors of matrices, SIAM J. Matrix Anal. Appl. 28 (2006), no. 2, 446–476. MR 2255338, DOI 10.1137/S0895479803436202
Terence Tao and Van Vu, The condition number of a randomly perturbed matrix, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 248–255. MR 2402448, DOI 10.1145/1250790.1250828
Terence Tao and Van Vu, Random matrices: the circular law, Commun. Contemp. Math. 10 (2008), no. 2, 261–307. MR 2409368, DOI 10.1142/S0219199708002788
Terence Tao and Van Vu, Smooth analysis of the condition number and the least singular value, Math. Comp. 79 (2010), no. 272, 2333–2352. MR 2684367, DOI 10.1090/S0025-5718-2010-02396-8
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170
Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algorithms 44 (2014), no. 2, 135–182. MR 3158627, DOI 10.1002/rsa.20429