Abstract
Let A = (aij) be an n × n random matrix with i.i.d. entries such that Ea11 = 0 and Ea 211 = 1. We prove that for any δ > 0 there is L > 0 depending only on δ, and a subset N of B n2 of cardinality at most exp(δn) such that with probability very close to one we have
. In fact, a stronger statement holds true. As an application, we show that for some L' > 0 and u ∈ [0, 1) depending only on the distribution law of a11, the smallest singular value sn of the matrix A satisfies
for all ε > 0. The latter result generalizes a theorem of Rudelson and Vershynin which was proved for random matrices with subgaussian entries.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R. Adamczak, A. E. Litvak, A. Pajor and N. Tomczak-Jaegermann, Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles, Journal of the American Mathematical Society 234 (2010), 535–561.
R. Adamczak, A. E. Litvak, A. Pajor and N. Tomczak-Jaegermann, Sharp bounds on the rate of convergence of empirical covariance matrix, Comptes Rendus Mathématique. Académie des Sciences. Paris 349 (2011), 195–200.
Z. D. Bai and Y. Q. Yin, Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Annals of Probability 21 (1993), 1275–1294.
A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM Journal on Matrix Analysis and Applications 9 (1988), 543–560.
O. Guedon, A. E. Litvak, A. Pajor and N. Tomczak-Jaegermann, On the interval of fluctuation of the singular values of random matrices, Journal of the European Mathematical Society 19 (2017), 1469–1505.
F. Götze, A. Naumov and A. Tikhomirov, On minimal singular values of random matrices with correlated entries, Random Matrices: Theory and Applications 4 (2015), 1550006.
W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963), 13–30.
V. Koltchinskii and S. Mendelson, Bounding the smallest singular value of a random matrix without concentration, International Mathematics Research Notices 23 (2015), 12991–13008.
R. Latala, Some estimates of norms of random matrices, Proceedings of the American Mathematical Society 133 (2005), 1273–1282.
C. Le, E. Levina and R. Vershynin, Concentration and regularization of random graphs, Random Structures & Algorithms 51 (2017), 538–561.
A. E. Litvak, A. Pajor, M. Rudelson and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Advances in Mathematics 195 (2005), 491–523.
S. Mendelson and G. Paouris, On the singular values of random matrices, Journal of the European Mathematical Society 16 (2014), 823–834.
V. D. Milman and G. Schechtman, Asymptotic Theory of Finite-dimensional Normed Spaces, Lecture Notes in Mathematics, Vol. 1200, Springer, Berlin, 1986.
H. H. Nguyen and S. O’Rourke, The elliptic law, International Mathematics Research Notices 17 (2015), 7620–7689.
G. Rempala and J. Wesolowski, Asymptotics for products of independent sums with an application toWishart determinants, Statistics & Probability Letters 74 (2005), 129–138.
B. A. Rogozin, On the increase of dispersion of sums of independent random variables, (Russian) Teorija Verojatnosteĭ i ee Primenenija 6 (1961), 106–108.
M. Rudelson, Lecture notes on non-aymptotic random matrix theory, Notes from the AMS Short Course on Random Matrices, 2013.
M. Rudelson and R. Vershynin, Non-asymptotic theory of random matrices: extreme singular values, in Proceedings of the International Congress of Mathematicians. Volume III, Hindustan Book Agency, New Delhi, 2010, pp. 1576–1602.
M. Rudelson and R. Vershynin, Smallest singular value of a random rectangular matrix, Communications on Pure and Applied Mathematics 62 (2009), 1707–1739.
M. Rudelson and R. Vershynin, The Littlewood–Offord problem and invertibility of random matrices, Advances in Mathematics 218 (2008), 600–633.
N. Srivastava and R. Vershynin, Covariance estimation for distributions with 2 + e moments, Annals of Probability 41 (2013), 3081–3111.
T. Tao and V. Vu, Inverse Littlewood–Offord theorems and the condition number of random discrete matrices, Annals of Mathematics 169 (2009), 595–632.
T. Tao and V. Vu, Random matrices: the circular law, Communications in Contemporary Mathematics 10 (2008), 261–307.
T. Tao and V. Vu, Random matrices: the distribution of the smallest singular values, Geometric and Functional Analysis 20 (2010), 260–297.
T. Tao and V. Vu, Smooth analysis of the condition number and the least singular value, Mathematics of Computation 79 (2010), 2333–2352.
H. Thorisson, Coupling, Stationarity, and Regeneration, Probability and its Applications (New York), Springer, New York, 2000.
K. Tikhomirov, The limit of the smallest singular value of random matrices with i.i.d. entries, Advances in Mathematics 284 (2015), 1–20.
K. E. Tikhomirov, The smallest singular value of random rectangular matrices with no moment assumptions on entries, Israel Journal of Mathematics 212 (2016), 289–314.
R. Vershynin, Introduction to the non-asymptotic analysis of random matrices, in Compressed Sensing: Theory and Applications, Cambridge University Press, Cambridge, 2012, pp. 210–268.
P. Yaskov, Lower bounds on the smallest eigenvalue of a sample covariance matrix, Electronic Communications in Probability 19 (2014), 10pp.
Y. Q. Yin, Z. D. Bai and P. R. Krishnaiah, On the limit of the largest eigenvalue of the large-dimensional sample covariance matrix, Probability Theory and Related Fields 78 (1988), 509–521.
Author information
Authors and Affiliations
Corresponding author
Additional information
E. R. was partially supported by U.S. Air Force grant F035062.
K. T. was partially supported by PIMS Graduate Scholarship and by Dean’s Excellence Award, Faculty of Science, UofA.
Rights and permissions
About this article
Cite this article
Rebrova, E., Tikhomirov, K. Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries. Isr. J. Math. 227, 507–544 (2018). https://doi.org/10.1007/s11856-018-1732-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-018-1732-y