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 TomczakJaegermann
Journal:
Proc. Amer. Math. Soc. 140 (2012), 987998
MSC (2010):
Primary 52A23, 46B06, 60B20, 60E15; Secondary 52A20, 46B09
Published electronically:
June 23, 2011
MathSciNet review:
2869083
Fulltext PDF
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 logconcave 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.
Radosław
Adamczak, Olivier
Guédon, Alexander
Litvak, Alain
Pajor, and Nicole
TomczakJaegermann, Smallest singular value of random matrices with
independent columns, C. R. Math. Acad. Sci. Paris 346
(2008), no. 1516, 853–856 (English, with English and French
summaries). MR
2441920 (2009h:15009), http://dx.doi.org/10.1016/j.crma.2008.07.011
 2.
Radosław
Adamczak, Alexander
E. Litvak, Alain
Pajor, and Nicole
TomczakJaegermann, Quantitative estimates of the
convergence of the empirical covariance matrix in logconcave
ensembles, J. Amer. Math. Soc.
23 (2010), no. 2,
535–561. MR 2601042
(2011c:60019), http://dx.doi.org/10.1090/S089403470900650X
 3.
R. Adamczak, A. Litvak, A. Pajor, N. TomczakJaegermann, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constructive Approximation, to appear (available online).
 4.
Christer
Borell, Convex measures on locally convex spaces, Ark. Mat.
12 (1974), 239–252. MR 0388475
(52 #9311)
 5.
Herm
Jan Brascamp and Elliott
H. Lieb, Best constants in Young’s inequality, its converse,
and its generalization to more than three functions, Advances in Math.
20 (1976), no. 2, 151–173. MR 0412366
(54 #492)
 6.
Alan
Edelman, Eigenvalues and condition numbers of random matrices,
SIAM J. Matrix Anal. Appl. 9 (1988), no. 4,
543–560. MR
964668 (89j:15039), http://dx.doi.org/10.1137/0609045
 7.
E.
Gluskin and V.
Milman, Geometric probability and random cotype 2, Geometric
aspects of functional analysis, Lecture Notes in Math., vol. 1850,
Springer, Berlin, 2004, pp. 123–138. MR 2087156
(2005h:60031), http://dx.doi.org/10.1007/9783540444893_12
 8.
Marius
Junge, Volume estimates for logconcave densities with application
to iterated convolutions, Pacific J. Math. 169
(1995), no. 1, 107–133. MR 1346249
(96i:46087)
 9.
A.
E. Litvak, A.
Pajor, M.
Rudelson, and N.
TomczakJaegermann, Smallest singular value of random matrices and
geometry of random polytopes, Adv. Math. 195 (2005),
no. 2, 491–523. MR 2146352
(2006g:52009), http://dx.doi.org/10.1016/j.aim.2004.08.004
 10.
A.
Pajor and L.
Pastur, On the limiting empirical measure of eigenvalues of the sum
of rank one matrices with logconcave distribution, Studia Math.
195 (2009), no. 1, 11–29. MR 2539559
(2010h:15022), http://dx.doi.org/10.4064/sm19512
 11.
G.
Paouris, Concentration of mass on convex bodies, Geom. Funct.
Anal. 16 (2006), no. 5, 1021–1049. MR 2276533
(2007k:52009), http://dx.doi.org/10.1007/s0003900605845
 12.
G. Paouris, Small ball probability estimates for logconcave measures, Trans. Amer. Math. Soc. (to appear).
 13.
Mark
Rudelson, Invertibility of random matrices: norm of the
inverse, Ann. of Math. (2) 168 (2008), no. 2,
575–600. MR 2434885
(2010f:46021), http://dx.doi.org/10.4007/annals.2008.168.575
 14.
Mark
Rudelson and Roman
Vershynin, The LittlewoodOfford problem and invertibility of
random matrices, Adv. Math. 218 (2008), no. 2,
600–633. MR 2407948
(2010g:60048), http://dx.doi.org/10.1016/j.aim.2008.01.010
 15.
Steve
Smale, On the efficiency of algorithms of
analysis, Bull. Amer. Math. Soc. (N.S.)
13 (1985), no. 2,
87–121. MR
799791 (86m:65061), http://dx.doi.org/10.1090/S027309791985153911
 16.
Stanisław
J. Szarek, Condition numbers of random matrices, J. Complexity
7 (1991), no. 2, 131–149. MR 1108773
(92i:65086), http://dx.doi.org/10.1016/0885064X(91)90002F
 17.
Terence
Tao and Van
H. Vu, Inverse LittlewoodOfford theorems and the condition number
of random discrete matrices, Ann. of Math. (2) 169
(2009), no. 2, 595–632. MR 2480613
(2010j:60110), http://dx.doi.org/10.4007/annals.2009.169.595
 1.
 R. Adamczak, O. Guédon, A.E. Litvak, A. Pajor, N. TomczakJaegermann, Smallest singular value of random matrices with independent columns, C. R. Math. Acad. Sci. Paris 346 (2008), no. 1516, 853856. MR 2441920 (2009h:15009)
 2.
 R. Adamczak, A.E. Litvak, A. Pajor, N. TomczakJaegermann, Quantitative estimates of the convergence of the empirical covariance matrix in logconcave Ensembles, J. Amer. Math. Soc. 23 (2010), no. 2, 535561. MR 2601042 (2011c:60019)
 3.
 R. Adamczak, A. Litvak, A. Pajor, N. TomczakJaegermann, 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), 239252. 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, 151173. MR 0412366 (54:492)
 6.
 A. Edelman, Eigenvalues and condition numbers of random matrices, SIAM J. of Matrix Anal. and Applic. 9 (1988), pp. 543560. MR 964668 (89j:15039)
 7.
 E. Gluskin, V. Milman, Geometric probability and random cotype , GAFA, 123138, Lecture Notes in Math., 1850, Springer, Berlin, 2004. MR 2087156 (2005h:60031)
 8.
 M. Junge, Volume estimates for logconcave densities with application to iterated convolutions, Pacific J. Math. 169 (1995), 107133. MR 1346249 (96i:46087)
 9.
 A. E. Litvak, A. Pajor, M. Rudelson, N. TomczakJaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), 491523. MR 2146352 (2006g:52009)
 10.
 A. Pajor, L. Pastur, On the limiting empirical measure of eigenvalues of the sum of rank one matrices with logconcave distribution, Studia Math. 195 (2009), no. 1, 1129. MR 2539559 (2010h:15022)
 11.
 G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16, no. 5 (2006), 10211049. MR 2276533 (2007k:52009)
 12.
 G. Paouris, Small ball probability estimates for logconcave 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), 575600. MR 2434885 (2010f:46021)
 14.
 M. Rudelson, R. Vershynin, The LittlewoodOfford Problem and invertibility of random matrices, Adv. Math. 218, No. 2 (2008), 600633. MR 2407948 (2010g:60048)
 15.
 S. Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. 13 (1985), 87121. MR 799791 (86m:65061)
 16.
 S. Szarek, Condition numbers of random matrices, J. Complexity 7 (1991), no. 2, 131149. MR 1108773 (92i:65086)
 17.
 T. Tao, V. Vu, Inverse LittlewoodOfford theorems and the condition number of random discrete matrices, Annals of Math. 169, No. 2 (2009), 595632. MR 2480613 (2010j:60110)
Similar Articles
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, 02097 Warszawa, Poland
Email:
radamcz@mimuw.edu.pl
Olivier Guédon
Affiliation:
Université ParisEst MarneLaVallée, Laboratoire d’Analyse et de Mathématiques Appliquées 5, boulevard Descartes, Champs sur Marne, 77454 MarnelaVallée, Cedex 2, France
Email:
olivier.guedon@univmlv.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é ParisEst MarneLaVallée, Laboratoire d’Analyse et de Mathématiques Appliquées, 5, boulevard Descartes, Champs sur Marne, 77454 MarnelaVallée, Cedex 2, France
Email:
Alain.Pajor@univmlv.fr
Nicole TomczakJaegermann
Affiliation:
Department of Mathematics and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada, T6G 2G1
Email:
nicole.tomczak@ualberta.ca
DOI:
http://dx.doi.org/10.1090/S000299392011109948
PII:
S 00029939(2011)109948
Keywords:
Condition number,
convex bodies,
logconcave 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
