×

Sparsity and non-Euclidean embeddings. (English) Zbl 1286.46015

Summary: We present a relation between sparsity and non-Euclidean isomorphic embeddings. We introduce a general restricted isomorphism property and show how it enables one to construct embeddings of \(\ell^n_p\), \(p>0\), into various types of Banach or quasi-Banach spaces. In particular, for \(0<r<p<2\) with \(r\leq 1\), we construct a family of operators that embed \(\ell^n_p\) into \(\ell_r^{(1 + \eta )n}\), with sharp polynomial bounds in \(\eta>0\).

MSC:

46B07 Local theory of Banach spaces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Adamczak, A. E. Litvak, A. Pajor and N. Tomczak-Jaegermann, Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling, Constructive Approximation 34 (2011), 61–88. · Zbl 1222.52009 · doi:10.1007/s00365-010-9117-4
[2] S. Artstein-Avidan, O.V. Milman and S. Sodin, Polynomial bounds for large Bernoulli sections of N 1 , Israel Journal of Mathematics 156 (2006), 141–155. · Zbl 1160.60004 · doi:10.1007/BF02773829
[3] J. Bastero and J. Bernués, Embedding l p n into r-Banach spaces, 0 &lt; r p &lt; 2, Journal of Mathematical Analysis and Applications 178 (1993), 363–380. · Zbl 0824.46026 · doi:10.1006/jmaa.1993.1313
[4] J. Bernués and M. López-Valdes, Tail estimates and a random embedding of l p n into $$\(\backslash\)ell _r\^{(1 + \(\backslash\)varepsilon )n}$$ , 0 &lt; r &lt; p &lt; 2, Publicationes Mathematicae Debrecen 70 (2007), 9–18. · Zbl 1170.60304
[5] E. J. Candès, J. K. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Communications on Pure and Applied Mathematics 59 (2006), 1207–1223. · Zbl 1098.94009 · doi:10.1002/cpa.20124
[6] E. J. Candès and T. Tao, Decoding by linear programming, IEEE Transactions on Information Theory 51 (2005), 4203–4215. · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[7] B. Carl and A. Pajor, Gelfand numbers of operators with values in a Hilbert space, Inventiones Mathematicae 94 (1988), 479–504. · Zbl 0668.47014 · doi:10.1007/BF01394273
[8] D. Chafai, G. Lecué, O. Guédon and A. Pajor, Interactions between Compressed Sensing, Random Matrices and High Dimensional Geometry, Panoramas et Synthèse, Société Mathématique de France, Vol. 37, 2012, to appear.
[9] D. L. Donoho, Compressed sensing, IEEE Transactions on Information Theory 52 (2006), 1289–1306. · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[10] S. Foucart and M.-J. Lai, Sparse recovery with pre-Gaussian random matrices, Studia Mathematica 200 (2010), 91–102. · Zbl 1205.15007 · doi:10.4064/sm200-1-6
[11] O. Friedland and O. Guédon, Random embedding of p n into 1 N , Mathematische Annalen 350 (2011), 953–972. · Zbl 1229.46009 · doi:10.1007/s00208-010-0581-8
[12] W. B. Johnson and G. Schechtman, Embedding l p m into l 1 n , Acta Mathematica 149 (1982), 71–85. · Zbl 0522.46015 · doi:10.1007/BF02392350
[13] W. B. Johnson and G. Schechtman, Very tight embeddings of subspaces of L p, 1 p &lt; 2, into l p n , Geometric and Functional Analysis 13 (2003), 845–851. · Zbl 1036.46008 · doi:10.1007/s00039-003-0432-9
[14] B. S. Kashin, The widths of certain finite-dimensional sets and classes of smooth functions, (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 41 (1977), no. 2, 334–351, 478.
[15] M. Ledoux and M. Talagrand, Probability in Banach Spaces, Springer-Verlag, Berlin, 1991, xii+480 pp. · Zbl 0748.60004
[16] R. LePage, M. Woodroofe and J. Zinn, Convergence to a stable distribution via order statistics, Annals of Probability 9 (1981), 624–632. · Zbl 0465.60031 · doi:10.1214/aop/1176994367
[17] B. Maurey and G. Pisier, Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach, (French) Studia Mathematica 58 (1976), 45–90. · Zbl 0344.47014
[18] S. Mendelson, A. Pajor and N. Tomczak-Jaegermann, Uniform uncertainty principle for Bernoulli and subgaussian ensembles, Constructive Approximation 28 (2008), 277–289. · Zbl 1230.46011 · doi:10.1007/s00365-007-9005-8
[19] A. Naor and A. Zvavitch, Isomorphic embedding of l p n , 1 &lt; p &lt; 2, into $$\(\backslash\)ell _1\^{(1 + \(\backslash\)varepsilon )n}$$ , Israel Journal of Mathematics 122 (2001), 371–380. · Zbl 1027.46010 · doi:10.1007/BF02809909
[20] G. Pisier, On the dimension of the l p n -subspaces of Banach spaces, for 1 p &lt; 2, Transactions of the American Mathematical Society 276 (1983), 201–211. · Zbl 0509.46016
[21] S. Rolewicz, Metric Linear Spaces, Monografie Matematyczne, Tom. 56 [Mathematical Monographs, Vol. 56], PWN-Polish Scientific Publishers, Warsaw, 1972, 287 pp. · Zbl 0226.46001
[22] G. Schechtman, Special orthogonal splittings of L 1 2k , Israel Journal of Mathematics 139 (2004), 337–347. · Zbl 1066.46010 · doi:10.1007/BF02787555
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.