Condition number of a square matrix with i.i.d. columns drawn from a convex body

Authors:
Radosław Adamczak, Olivier Guédon, Alexander E. Litvak, Alain Pajor and Nicole Tomczak-Jaegermann

Journal:
Proc. Amer. Math. Soc. **140** (2012), 987-998

MSC (2010):
Primary 52A23, 46B06, 60B20, 60E15; Secondary 52A20, 46B09

DOI:
https://doi.org/10.1090/S0002-9939-2011-10994-8

Published electronically:
June 23, 2011

MathSciNet review:
2869083

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We study the smallest singular value of a square random matrix with i.i.d. columns drawn from an isotropic log-concave distribution. An important example is obtained by sampling vectors uniformly distributed in an isotropic convex body. We deduce that the condition number of such matrices is of the order of the size of the matrix and give an estimate on its tail behaviour.

**1.**R. Adamczak, O. Guédon, A.E. Litvak, A. Pajor, N. Tomczak-Jaegermann,*Smallest singular value of random matrices with independent columns*, C. R. Math. Acad. Sci. Paris 346 (2008), no. 15-16, 853-856. MR**2441920 (2009h:15009)****2.**R. Adamczak, A.E. Litvak, A. Pajor, N. Tomczak-Jaegermann,*Quantitative estimates of the convergence of the empirical covariance matrix in log-concave Ensembles,*J. Amer. Math. Soc. 23 (2010), no. 2, 535-561. MR**2601042 (2011c:60019)****3.**R. Adamczak, A. Litvak, A. Pajor, N. Tomczak-Jaegermann,*Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling,*Constructive Approximation, to appear (available online).**4.**C. Borell,*Convex measures on locally convex spaces,*Ark. Mat. 12 (1974), 239-252. MR**0388475 (52:9311)****5.**H.J. Brascamp, E.H. Lieb,*Best constants in Young's inequality, its converse, and its generalization to more than three functions*, Adv. Math. 20 (1976), no. 2, 151-173. MR**0412366 (54:492)****6.**A. Edelman,*Eigenvalues and condition numbers of random matrices*, SIAM J. of Matrix Anal. and Applic. 9 (1988), pp. 543-560. MR**964668 (89j:15039)****7.**E. Gluskin, V. Milman,*Geometric probability and random cotype*, GAFA, 123-138, Lecture Notes in Math., 1850, Springer, Berlin, 2004. MR**2087156 (2005h:60031)****8.**M. Junge,*Volume estimates for log-concave densities with application to iterated convolutions*, Pacific J. Math. 169 (1995), 107-133. MR**1346249 (96i:46087)****9.**A. E. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann,*Smallest singular value of random matrices and geometry of random polytopes*, Adv. Math. 195 (2005), 491-523. MR**2146352 (2006g:52009)****10.**A. Pajor, L. Pastur,*On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution*, Studia Math. 195 (2009), no. 1, 11-29. MR**2539559 (2010h:15022)****11.**G. Paouris,*Concentration of mass on convex bodies*, Geom. Funct. Anal. 16, no. 5 (2006), 1021-1049. MR**2276533 (2007k:52009)****12.**G. Paouris,*Small ball probability estimates for log-concave measures*, Trans. Amer. Math. Soc. (to appear).**13.**M. Rudelson,*Invertibility of random matrices: norm of the inverse*, Annals of Math. 168, No. 2 (2008), 575-600. MR**2434885 (2010f:46021)****14.**M. Rudelson, R. Vershynin,*The Littlewood-Offord Problem and invertibility of random matrices*, Adv. Math. 218, No. 2 (2008), 600-633. MR**2407948 (2010g:60048)****15.**S. Smale,*On the efficiency of algorithms of analysis*, Bull. Amer. Math. Soc. 13 (1985), 87-121. MR**799791 (86m:65061)****16.**S. Szarek,*Condition numbers of random matrices*, J. Complexity 7 (1991), no. 2, 131-149. MR**1108773 (92i:65086)****17.**T. Tao, V. Vu,*Inverse Littlewood-Offord theorems and the condition number of random discrete matrices*, Annals of Math. 169, No. 2 (2009), 595-632. MR**2480613 (2010j:60110)**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
52A23,
46B06,
60B20,
60E15,
52A20,
46B09

Retrieve articles in all journals with MSC (2010): 52A23, 46B06, 60B20, 60E15, 52A20, 46B09

Additional Information

**Radosław Adamczak**

Affiliation:
Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland

Email:
radamcz@mimuw.edu.pl

**Olivier Guédon**

Affiliation:
Université Paris-Est Marne-La-Vallée, Laboratoire d’Analyse et de Mathématiques Appliquées 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallée, Cedex 2, France

Email:
olivier.guedon@univ-mlv.fr

**Alexander E. Litvak**

Affiliation:
Department of Mathematics and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1

Email:
alexandr@math.ualberta.ca

**Alain Pajor**

Affiliation:
Université Paris-Est Marne-La-Vallée, Laboratoire d’Analyse et de Mathématiques Appliquées, 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallée, Cedex 2, France

Email:
Alain.Pajor@univ-mlv.fr

**Nicole Tomczak-Jaegermann**

Affiliation:
Department of Mathematics and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1

Email:
nicole.tomczak@ualberta.ca

DOI:
https://doi.org/10.1090/S0002-9939-2011-10994-8

Keywords:
Condition number,
convex bodies,
log-concave distributions,
isotropic distributions,
random matrix,
norm of a random matrix,
smallest singular number

Received by editor(s):
October 4, 2010

Received by editor(s) in revised form:
December 6, 2010

Published electronically:
June 23, 2011

Additional Notes:
A part of this work was done when the first author held a postdoctoral position at the Department of Mathematical and Statistical Sciences, University of Alberta in Edmonton, Alberta. The position was sponsored by the Pacific Institute for the Mathematical Sciences. Research was partially supported by MNiSW Grant No. N N201 397437 and the Foundation for Polish Science.

The fifth author holds the Canada Research Chair in Geometric Analysis.

Communicated by:
Marius Junge

Article copyright:
© Copyright 2011
American Mathematical Society