Condition number of a square matrix with i.i.d. columns drawn from a convex body
HTML articles powered by AMS MathViewer
- by Radosław Adamczak, Olivier Guédon, Alexander E. Litvak, Alain Pajor and Nicole Tomczak-Jaegermann PDF
- Proc. Amer. Math. Soc. 140 (2012), 987-998 Request permission
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.References
- Radosław Adamczak, Olivier Guédon, Alexander Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann, Smallest singular value of random matrices with independent columns, C. R. Math. Acad. Sci. Paris 346 (2008), no. 15-16, 853–856 (English, with English and French summaries). MR 2441920, DOI 10.1016/j.crma.2008.07.011
- Radosław Adamczak, Alexander E. Litvak, Alain Pajor, and Nicole 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, DOI 10.1090/S0894-0347-09-00650-X
- 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).
- Christer Borell, Convex measures on locally convex spaces, Ark. Mat. 12 (1974), 239–252. MR 388475, DOI 10.1007/BF02384761
- 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 412366, DOI 10.1016/0001-8708(76)90184-5
- 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
- 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, DOI 10.1007/978-3-540-44489-3_{1}2
- Marius Junge, Volume estimates for log-concave densities with application to iterated convolutions, Pacific J. Math. 169 (1995), no. 1, 107–133. MR 1346249
- A. E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, Adv. Math. 195 (2005), no. 2, 491–523. MR 2146352, DOI 10.1016/j.aim.2004.08.004
- A. Pajor and 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, DOI 10.4064/sm195-1-2
- G. Paouris, Concentration of mass on convex bodies, Geom. Funct. Anal. 16 (2006), no. 5, 1021–1049. MR 2276533, DOI 10.1007/s00039-006-0584-5
- G. Paouris, Small ball probability estimates for log-concave measures, Trans. Amer. Math. Soc. (to appear).
- Mark Rudelson, Invertibility of random matrices: norm of the inverse, Ann. of Math. (2) 168 (2008), no. 2, 575–600. MR 2434885, DOI 10.4007/annals.2008.168.575
- 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
- Steve Smale, On the efficiency of algorithms of analysis, Bull. Amer. Math. Soc. (N.S.) 13 (1985), no. 2, 87–121. MR 799791, DOI 10.1090/S0273-0979-1985-15391-1
- Stanisław J. Szarek, Condition numbers of random matrices, J. Complexity 7 (1991), no. 2, 131–149. MR 1108773, DOI 10.1016/0885-064X(91)90002-F
- Terence Tao and Van H. Vu, Inverse Littlewood-Offord theorems and the condition number of random discrete matrices, Ann. of Math. (2) 169 (2009), no. 2, 595–632. MR 2480613, DOI 10.4007/annals.2009.169.595
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
- MR Author ID: 367520
- 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
- MR Author ID: 173265
- Email: nicole.tomczak@ualberta.ca
- 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
- © Copyright 2011 American Mathematical Society
- 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
- MathSciNet review: 2869083