Lower estimates for the singular values of random matrices

Mark Rudelson

doi:10.1016/j.crma.2005.11.013

Functional Analysis/Probability Theory

Lower estimates for the singular values of random matrices
[Minorations des valeurs singulières de matrices aléatoires]

Présenté par : Gilles Pisier

Mark Rudelson ¹

¹ Department of Mathematics, University of Missouri, Columbia, MO 65211, USA

Comptes Rendus. Mathématique, Volume 342 (2006) no. 4, pp. 247-252.

Résumé
Abstract

Soit Γ une matrice $n \times n$ , ayant pour coefficients des variables aléatoires indépendantes et identiquement distribuées (i.i.d.) vérifiant une décroissance sous-gaussienne des queues. Dans ce travail, nous obtenons des minorations de type polynomial des valeurs singulières de Γ, valables avec une probabilité proche de 1. Nous montrons aussi que si A est une matrice $N \times n$ avec $N > n$ , dont les coefficients sont des variables aléatoires sous-gaussiennes i.i.d., alors l'espace $E = A R^{n}$ vérifie avec une grande probablilité les conditions du théorème de Kashin, c'est à dire les normes $ℓ_{2}^{N}$ et $ℓ_{1}^{N}$ sont équivalentes sur E. De plus la distance entre ces normes dépend polynomialement de $δ = (N - n) / n$ .

Let Γ be an $n \times n$ matrix, whose entries are independent identically distributed (i.i.d.) random variables satisfying the subgaussian tail estimate. We obtain polynomial type lower estimates of the singular numbers of Γ, which hold with probability close to 1. We also show that if A is an $N \times n$ matrix with $N > n$ , whose entries are i.i.d. subgaussian random variables, then with high probability the space $E = A R^{n}$ satisfies the conditions of Kashin's theorem, i.e. the $ℓ_{2}^{N}$ and $ℓ_{1}^{N}$ norms are equivalent on E. Moreover the distance between these norms polynomially depends on $δ = (N - n) / n$ .

Reçu le : 2005-10-10
Accepté le : 2005-11-15
Publié le : 2006-01-04

DOI : 10.1016/j.crma.2005.11.013

Affiliations des auteurs :

Mark Rudelson ¹

¹ Department of Mathematics, University of Missouri, Columbia, MO 65211, USA

@article{CRMATH_2006__342_4_247_0,
     author = {Mark Rudelson},
     title = {Lower estimates for the singular values of random matrices},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {247--252},
     publisher = {Elsevier},
     volume = {342},
     number = {4},
     year = {2006},
     doi = {10.1016/j.crma.2005.11.013},
     language = {en},
}

TY  - JOUR
AU  - Mark Rudelson
TI  - Lower estimates for the singular values of random matrices
JO  - Comptes Rendus. Mathématique
PY  - 2006
SP  - 247
EP  - 252
VL  - 342
IS  - 4
PB  - Elsevier
DO  - 10.1016/j.crma.2005.11.013
LA  - en
ID  - CRMATH_2006__342_4_247_0
ER  -

%0 Journal Article
%A Mark Rudelson
%T Lower estimates for the singular values of random matrices
%J Comptes Rendus. Mathématique
%D 2006
%P 247-252
%V 342
%N 4
%I Elsevier
%R 10.1016/j.crma.2005.11.013
%G en
%F CRMATH_2006__342_4_247_0

Mark Rudelson. Lower estimates for the singular values of random matrices. Comptes Rendus. Mathématique, Volume 342 (2006) no. 4, pp. 247-252. doi : 10.1016/j.crma.2005.11.013. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2005.11.013/

Bibliographie
Cité par

[1] S. Artstein, O. Friedland, V. Milman, Large sections of $L_{1}^{n}$ spanned by random sign-vectors are isomorphic to Euclidean with polynomial dependence, Preprint

[2] Z.D. Bai; Y.Q. Yin Limit of the smallest eigenvalue of a large-dimensional sample covariance matrix, Ann. Probab., Volume 21 (1993) no. 3, pp. 1275-1294

[3] K. Davidson; S.J. Szarek Local operator theory, random matrices and Banach spaces, Handbook of the Geometry of Banach Spaces, vol. I, North-Holland, Amsterdam, 2001, pp. 317-366

[4] A.Yu. Garnaev; E.D. Gluskin The widths of a Euclidean ball, Dokl. Akad. Nauk SSSR, Volume 277 (1984), pp. 1048-1052 (in Russian). English translation Soviet Math. Dokl., 30, 1984, pp. 200-204

[5] B. Kashin The widths of certain finite-dimensional sets and classes of smooth functions, Izv. Akad. Nauk SSSR Ser. Mat., Volume 41 (1977), pp. 334-351 (in Russian)

[6] A.E. Litvak; A. Pajor; M. Rudelson; N. Tomczak-Jaegermann Smallest singular value of random matrices and geometry of random polytopes, Adv. Math., Volume 195 (2005) no. 2, pp. 491-523

[7] A.E. Litvak; A. Pajor; M. Rudelson; N. Tomczak-Jaegermann; R. Vershynin Random Euclidean embeddings in spaces of bounded volume ratio, C. R. Acad. Sci. Paris, Ser. I, Volume 339 (2004), pp. 33-38

[8] A.E. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, R. Vershynin, Euclidean embeddings in spaces of finite volume ratio via random matrices, J. Reine Angew. Math., in press

[9] M. Rudelson, Invertibility of random matrices: norm of the inverse, Preprint

Kateryna Tatarko An upper bound on the smallest singular value of a square random matrix, Journal of Complexity, Volume 48 (2018), p. 119 | DOI:10.1016/j.jco.2018.06.002
Richard Lechner; Markus Passenbrunner; Joscha Prochno Estimating Averages of Order Statistics of Bivariate Functions, Journal of Theoretical Probability, Volume 30 (2017) no. 4, p. 1445 | DOI:10.1007/s10959-016-0702-8
Nicholas A. Cook On the singularity of adjacency matrices for random regular digraphs, Probability Theory and Related Fields, Volume 167 (2017) no. 1-2, p. 143 | DOI:10.1007/s00440-015-0679-8
Robert Qiu; Michael Wicks Non-asymptotic, Local Theory of Random Matrices, Cognitive Networked Sensing and Big Data (2014), p. 271 | DOI:10.1007/978-1-4614-4544-9_5
Mark Rudelson Row products of random matrices, Advances in Mathematics, Volume 231 (2012) no. 6, p. 3199 | DOI:10.1016/j.aim.2012.08.010
Yehoram Gordon; Alexander E. Litvak; Carsten Schütt; Elisabeth Werner Uniform estimates for order statistics and Orlicz functions, Positivity, Volume 16 (2012) no. 1, p. 1 | DOI:10.1007/s11117-010-0107-3
Venkatesh Saligrama; Manqi Zhao Thresholded Basis Pursuit: LP Algorithm for Order-Wise Optimal Support Recovery for Sparse and Approximately Sparse Signals From Noisy Random Measurements, IEEE Transactions on Information Theory, Volume 57 (2011) no. 3, p. 1567 | DOI:10.1109/tit.2011.2104512
Roman Vershynin Spectral norm of products of random and deterministic matrices, Probability Theory and Related Fields, Volume 150 (2011) no. 3-4, p. 471 | DOI:10.1007/s00440-010-0281-z
Terence Tao; Van Vu Random Matrices: the Distribution of the Smallest Singular Values, Geometric and Functional Analysis, Volume 20 (2010) no. 1, p. 260 | DOI:10.1007/s00039-010-0057-8
Mark Rudelson; Roman Vershynin Smallest singular value of a random rectangular matrix, Communications on Pure and Applied Mathematics, Volume 62 (2009) no. 12, p. 1707 | DOI:10.1002/cpa.20294
Omer Friedland; Sasha Sodin An extension of a Bourgain–Lindenstrauss–Milman inequality, Journal of Functional Analysis, Volume 251 (2007) no. 2, p. 492 | DOI:10.1016/j.jfa.2007.07.004

Cité par 11 documents. Sources : Crossref

Commentaires - Politique

Il n'y a aucun commentaire pour cet article. Soyez le premier à écrire un commentaire !

Publier un nouveau commentaire:

Publier une nouvelle réponse: