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
Additional Information
- Brendan Farrell
- Affiliation: Computing and Mathematical Sciences, California Institute of Technology, 1200 E. California Boulevard, Pasadena, California 91125
- Email: farrell@cms.caltech.edu
- Roman Vershynin
- Affiliation: Department of Mathematics, University of Michigan, 530 Church St., Ann Arbor, Michigan 48109
- MR Author ID: 636015
- Email: romanv@umich.edu
- Received by editor(s): September 26, 2014
- Received by editor(s) in revised form: May 29, 2015
- Published electronically: October 6, 2015
- Additional Notes: The first author was partially supported by Joel A. Tropp under ONR awards N00014-08-1-0883 and N00014-11-1002 and a Sloan Research Fellowship
The second author was partially supported by NSF grants 1001829, 1265782, and U.S. Air Force Grant FA9550-14-1-0009. - Communicated by: Mark M. Meerschaert
- © Copyright 2015 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 144 (2016), 2257-2261
- MSC (2010): Primary 60B20
- DOI: https://doi.org/10.1090/proc/12844
- MathSciNet review: 3460183