We study the Restricted Isometry Property of a random matrix Γ with independent isotropic log-concave rows. To this end, we introduce a parameter 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.
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 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.
Accepted:
Published online:
Radosław Adamczak 1; Rafał Latała 1; Alexander E. Litvak 2; Alain Pajor 3; Nicole Tomczak-Jaegermann 2
@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/
[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] Smallest singular value of random matrices with independent columns, C. R. Acad. Sci. Paris, Ser. I, Volume 346 (2008), pp. 853-856
[3] Quantitative estimates of the convergence of the empirical covariance matrix in log-concave Ensembles, Journal of AMS, Volume 234 (2010), pp. 535-561
[4] Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constructive Approximation, Volume 34 (2011), pp. 61-88
[5] 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] 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] Decoding by linear programming, IEEE Trans. Inform. Theory, Volume 51 (2005), pp. 4203-4215
[10] Neighborly Polytopes and Sparse Solutions of Underdetermined Linear Equations, Department of Statistics, Stanford University, 2005
[11] Random walks and volume algorithm for convex bodies, Random Structures and Algorithms, Volume 2 (1997), pp. 1-50
[12] Order statistics and concentration of norms for log-concave vectors, J. Funct. Anal., Volume 261 (2011), pp. 681-696
[13] Empirical processes with a bounded diameter, Geom. Funct. Anal., Volume 20 (2010), pp. 988-1027
[14] Reconstruction and subgaussian operators in asymptotic geometric analysis, Geom. Funct. Anal., Volume 17 (2007), pp. 1248-1282
[15] Concentration of mass on convex bodies, Geom. Funct. Anal., Volume 16 (2006), pp. 1021-1049
Cited by Sources:
Comments - Policy