Some applications of Ball’s extension theorem
HTML articles powered by AMS MathViewer
- by Manor Mendel and Assaf Naor PDF
- Proc. Amer. Math. Soc. 134 (2006), 2577-2584 Request permission
Abstract:
We present two applications of Ball’s extension theorem. First we observe that Ball’s extension theorem, together with the recent solution of Ball’s Markov type $2$ problem due to Naor, Peres, Schramm and Sheffield, imply a generalization, and an alternative proof of, the Johnson-Lindenstrauss extension theorem. Second, we prove that the distortion required to embed the integer lattice $\{0,1,\ldots ,m\}^n$, equipped with the $\ell _p^n$ metric, in any $2$-uniformly convex Banach space is of order $\min \left \{n^{\frac 12-\frac {1}{p}},m^{1-\frac {2}{p}}\right \}$.References
- K. Ball, Markov chains, Riesz transforms and Lipschitz maps, Geom. Funct. Anal. 2 (1992), no. 2, 137–172. MR 1159828, DOI 10.1007/BF01896971
- Keith Ball, Eric A. Carlen, and Elliott H. Lieb, Sharp uniform convexity and smoothness inequalities for trace norms, Invent. Math. 115 (1994), no. 3, 463–482. MR 1262940, DOI 10.1007/BF01231769
- Boris Begun, A remark on almost extensions of Lipschitz functions, Israel J. Math. 109 (1999), 151–155. MR 1679594, DOI 10.1007/BF02775032
- Yoav Benyamini and Joram Lindenstrauss, Geometric nonlinear functional analysis. Vol. 1, American Mathematical Society Colloquium Publications, vol. 48, American Mathematical Society, Providence, RI, 2000. MR 1727673, DOI 10.1090/coll/048
- J. Bourgain, Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms, Geometrical aspects of functional analysis (1985/86), Lecture Notes in Math., vol. 1267, Springer, Berlin, 1987, pp. 157–167. MR 907692, DOI 10.1007/BFb0078143
- J. Bourgain, V. Milman, and H. Wolfson, On type of metric spaces, Trans. Amer. Math. Soc. 294 (1986), no. 1, 295–317. MR 819949, DOI 10.1090/S0002-9947-1986-0819949-8
- B. Brinkman and M. Charikar. On the impossibility of dimension reduction in $\ell _1$. In Proceedings of the 44th Annual IEEE Conference on Foundations of Computer Science. ACM, 2003.
- Per Enflo, On the nonexistence of uniform homeomorphisms between $L_{p}$-spaces, Ark. Mat. 8 (1969), 103–105. MR 271719, DOI 10.1007/BF02589549
- William B. Johnson and Joram Lindenstrauss, Extensions of Lipschitz mappings into a Hilbert space, Conference in modern analysis and probability (New Haven, Conn., 1982) Contemp. Math., vol. 26, Amer. Math. Soc., Providence, RI, 1984, pp. 189–206. MR 737400, DOI 10.1090/conm/026/737400
- J. R. Lee, M. Mendel, and A. Naor. Metric structures in $L_1$: Dimension, snowflakes, and average distortion. European J. Combin., 2004. To appear.
- James R. Lee and Assar Naor, Absolute Lipschitz extendability, C. R. Math. Acad. Sci. Paris 338 (2004), no. 11, 859–862 (English, with English and French summaries). MR 2059662, DOI 10.1016/j.crma.2004.03.005
- J. R. Lee and A. Naor, Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$, Geom. Funct. Anal. 14 (2004), no. 4, 745–747. MR 2084978, DOI 10.1007/s00039-004-0473-8
- James R. Lee and Assaf Naor, Extending Lipschitz functions via random metric partitions, Invent. Math. 160 (2005), no. 1, 59–95. MR 2129708, DOI 10.1007/s00222-004-0400-5
- Joram Lindenstrauss and Lior Tzafriri, Classical Banach spaces. II, Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], vol. 97, Springer-Verlag, Berlin-New York, 1979. Function spaces. MR 540367, DOI 10.1007/978-3-662-35347-9
- Nathan Linial, Eran London, and Yuri Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica 15 (1995), no. 2, 215–245. MR 1337355, DOI 10.1007/BF01200757
- M. B. Marcus and G. Pisier, Characterizations of almost surely continuous $p$-stable random Fourier series and strongly stationary processes, Acta Math. 152 (1984), no. 3-4, 245–301. MR 741056, DOI 10.1007/BF02392199
- Jiří Matoušek, On embedding expanders into $l_p$ spaces, Israel J. Math. 102 (1997), 189–197. MR 1489105, DOI 10.1007/BF02773799
- Bernard Maurey and Gilles Pisier, Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach, Studia Math. 58 (1976), no. 1, 45–90 (French). MR 443015, DOI 10.4064/sm-58-1-45-90
- M. Mendel and A. Naor. Metric cotype. Manuscript, 2004.
- Vitali D. Milman and Gideon Schechtman, Asymptotic theory of finite-dimensional normed spaces, Lecture Notes in Mathematics, vol. 1200, Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov. MR 856576
- Assaf Naor, A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between $L_p$ spaces, Mathematika 48 (2001), no. 1-2, 253–271 (2003). MR 1996375, DOI 10.1112/S0025579300014480
- A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Preprint, 2004.
- Assaf Naor and Gideon Schechtman, Remarks on non linear type and Pisier’s inequality, J. Reine Angew. Math. 552 (2002), 213–236. MR 1940437, DOI 10.1515/crll.2002.092
- Gilles Pisier, Probabilistic methods in the geometry of Banach spaces, Probability and analysis (Varenna, 1985) Lecture Notes in Math., vol. 1206, Springer, Berlin, 1986, pp. 167–241. MR 864714, DOI 10.1007/BFb0076302
- Michel Talagrand, Embedding subspaces of $L_1$ into $l^N_1$, Proc. Amer. Math. Soc. 108 (1990), no. 2, 363–369. MR 994792, DOI 10.1090/S0002-9939-1990-0994792-4
- Nicole Tomczak-Jaegermann, Banach-Mazur distances and finite-dimensional operator ideals, Pitman Monographs and Surveys in Pure and Applied Mathematics, vol. 38, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989. MR 993774
- Santosh S. Vempala, The random projection method, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 65, American Mathematical Society, Providence, RI, 2004. With a foreword by Christos H. Papadimitriou. MR 2073630, DOI 10.1090/dimacs/065
- J. H. Wells and L. R. Williams, Embeddings and extensions in analysis, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84, Springer-Verlag, New York-Heidelberg, 1975. MR 0461107, DOI 10.1007/978-3-642-66037-5
Additional Information
- Manor Mendel
- Affiliation: Department of Computer Science, California Institute of Technology, Pasadena, California 91125
- Address at time of publication: Computer Science Division, The Open University of Israel, 108 Ravutski Street, P.O.B. 808, Raanana 43107, Israel
- Email: manorme@openu.ac.il
- Assaf Naor
- Affiliation: Theory Group, Microsoft Research, Redmond, Washington 90852
- Email: anaor@microsoft.com
- Received by editor(s): January 27, 2005
- Received by editor(s) in revised form: March 18, 2005
- Published electronically: February 17, 2006
- Communicated by: David Preiss
- © Copyright 2006 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 134 (2006), 2577-2584
- MSC (2000): Primary 46B20; Secondary 51F99
- DOI: https://doi.org/10.1090/S0002-9939-06-08298-0
- MathSciNet review: 2213735