Geometry of log-concave ensembles of random matrices and approximate reconstruction

Radosław Adamczak; Rafał Latała; Alexander E. Litvak; Alain Pajor; Nicole Tomczak-Jaegermann

doi:10.1016/j.crma.2011.06.025

Functional Analysis/Probability Theory

Geometry of log-concave ensembles of random matrices and approximate reconstruction
[Géométrie des ensembles log-concave des matrices aléatoires et une reconstruction approximative]

Présenté par : Gilles Pisier

Radosław Adamczak ¹ ; Rafał Latała ¹ ; Alexander E. Litvak ² ; Alain Pajor ³ ; Nicole Tomczak-Jaegermann ²

¹ Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
³ Equipe dʼanalyse et mathématiques appliquées, université Paris Est, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallee cedex 2, France

Comptes Rendus. Mathématique, Volume 349 (2011) no. 13-14, pp. 783-786.

Résumé
Abstract

On étudie la propriété dʼisométrie restreinte dʼune matrice aléatoire Γ dont les lignes sont des vecteurs aléatoires indépendants isotropes log-concave. Pour cela on introduit un paramètre $Γ_{k, m}$ qui contrôle uniformément les normes dʼopérateurs des sous-matrices de k lignes et m colonnes. Ce paramètre est estimé à lʼaide de nouvelles inégalités de queue des statistiques dʼordre et dʼinégalités de déviation des normes de projections dʼun vecteur aléatoire log-concave.

We study the Restricted Isometry Property of a random matrix Γ with independent isotropic log-concave rows. To this end, we introduce a parameter $Γ_{k, m}$ that controls uniformly the operator norm of sub-matrices with k rows and m columns. This parameter is estimated by means of new tail estimates of order statistics and deviation inequalities for norms of projections of an isotropic log-concave vector.

Reçu le : 2011-02-28
Accepté le : 2011-06-29
Publié le : 2011-07-01

DOI : 10.1016/j.crma.2011.06.025

Affiliations des auteurs :

Radosław Adamczak ¹ ; Rafał Latała ¹ ; Alexander E. Litvak ² ; Alain Pajor ³ ; Nicole Tomczak-Jaegermann ²

¹ Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland
² Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, Canada T6G 2G1
³ Equipe dʼanalyse et mathématiques appliquées, université Paris Est, 5, boulevard Descartes, Champs-sur-Marne, 77454 Marne-la-Vallee cedex 2, France

@article{CRMATH_2011__349_13-14_783_0,
     author = {Rados{\l}aw Adamczak and Rafa{\l} Lata{\l}a and Alexander E. Litvak and Alain Pajor and Nicole Tomczak-Jaegermann},
     title = {Geometry of log-concave ensembles of random matrices and approximate reconstruction},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {783--786},
     publisher = {Elsevier},
     volume = {349},
     number = {13-14},
     year = {2011},
     doi = {10.1016/j.crma.2011.06.025},
     language = {en},
}

TY  - JOUR
AU  - Radosław Adamczak
AU  - Rafał Latała
AU  - Alexander E. Litvak
AU  - Alain Pajor
AU  - Nicole Tomczak-Jaegermann
TI  - Geometry of log-concave ensembles of random matrices and approximate reconstruction
JO  - Comptes Rendus. Mathématique
PY  - 2011
SP  - 783
EP  - 786
VL  - 349
IS  - 13-14
PB  - Elsevier
DO  - 10.1016/j.crma.2011.06.025
LA  - en
ID  - CRMATH_2011__349_13-14_783_0
ER  -

%0 Journal Article
%A Radosław Adamczak
%A Rafał Latała
%A Alexander E. Litvak
%A Alain Pajor
%A Nicole Tomczak-Jaegermann
%T Geometry of log-concave ensembles of random matrices and approximate reconstruction
%J Comptes Rendus. Mathématique
%D 2011
%P 783-786
%V 349
%N 13-14
%I Elsevier
%R 10.1016/j.crma.2011.06.025
%G en
%F CRMATH_2011__349_13-14_783_0

Radosław Adamczak; Rafał Latała; Alexander E. Litvak; Alain Pajor; Nicole Tomczak-Jaegermann. Geometry of log-concave ensembles of random matrices and approximate reconstruction. Comptes Rendus. Mathématique, Volume 349 (2011) no. 13-14, pp. 783-786. doi : 10.1016/j.crma.2011.06.025. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2011.06.025/

Bibliographie
Cité par

[1] R. Adamczak, O. Guédon, A.E. Litvak, A. Pajor, N. Tomczak-Jaegermann, Condition number of a square matrix with i.i.d. columns drawn from a convex body, Proc. Amer. Math. Soc., , in press. | DOI

[2] R. Adamczak; O. Guédon; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann Smallest singular value of random matrices with independent columns, C. R. Acad. Sci. Paris, Ser. I, Volume 346 (2008), pp. 853-856

[3] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann Quantitative estimates of the convergence of the empirical covariance matrix in log-concave Ensembles, Journal of AMS, Volume 234 (2010), pp. 535-561

[4] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constructive Approximation, Volume 34 (2011), pp. 61-88

[5] R. Adamczak; A.E. Litvak; A. Pajor; N. Tomczak-Jaegermann Sharp bounds on the rate of convergence of empirical covariance matrix, C. R. Acad. Sci. Paris, Ser. I, Volume 349 (2011), pp. 195-200

[6] R. Adamczak, R. Latała, A.E. Litvak, A. Pajor, N. Tomczak-Jaegermann, Tail estimates for norms of sums of log-concave random vectors, preprint, available at . | arXiv

[7] R. Adamczak, R. Latała, A.E. Litvak, A. Pajor, N. Tomczak-Jaegermann, Chevet type inequality and norms of submatrices, preprint, available at . | arXiv

[8] J. Bourgain Random points in isotropic convex sets, Berkeley, CA, 1996 (Math. Sci. Res. Inst. Publ.), Volume vol. 34, Cambridge Univ. Press, Cambridge (1999), pp. 53-58

[9] E.J. Candés; T. Tao Decoding by linear programming, IEEE Trans. Inform. Theory, Volume 51 (2005), pp. 4203-4215

[10] D.L. Donoho Neighborly Polytopes and Sparse Solutions of Underdetermined Linear Equations, Department of Statistics, Stanford University, 2005

[11] R. Kannan; L. Lovász; M. Simonovits Random walks and $O^{⁎} (n^{5})$ volume algorithm for convex bodies, Random Structures and Algorithms, Volume 2 (1997), pp. 1-50

[12] R. Latała Order statistics and concentration of $l_{r}$ norms for log-concave vectors, J. Funct. Anal., Volume 261 (2011), pp. 681-696

[13] S. Mendelson Empirical processes with a bounded $ψ_{1}$ diameter, Geom. Funct. Anal., Volume 20 (2010), pp. 988-1027

[14] S. Mendelson; A. Pajor; N. Tomczak-Jaegermann Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. Funct. Anal., Volume 17 (2007), pp. 1248-1282

[15] G. Paouris Concentration of mass on convex bodies, Geom. Funct. Anal., Volume 16 (2006), pp. 1021-1049

Cité par Sources :

Commentaires - Politique