Lipschitz representations of subsets of the cube

Mendelson, Shahar

doi:10.1090/S0002-9939-06-08620-5

Lipschitz representations of subsets of the cube
HTML articles powered by AMS MathViewer

by Shahar Mendelson PDF

Proc. Amer. Math. Soc. 135 (2007), 1455-1463 Request permission

Abstract:

We show that for any class of uniformly bounded functions $H$ with a reasonable combinatorial dimension, the vast majority of small subsets of the $n$-dimensional combinatorial cube cannot be represented as a Lipschitz image of a subset of $H$, unless the Lipschitz constant is very large. We apply this result to the case when $H$ consists of linear functionals of norm at most one on a Hilbert space.

References

Shai Ben-David, Nadav Eiron, and Hans Ulrich Simon, Limitations of learning via embeddings in Euclidean half spaces, J. Mach. Learn. Res. 3 (2002), no. Spec. Issue Comput. Learn. Theory, 441–461. MR 1984025, DOI 10.1162/153244303321897681
Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
Jürgen Forster, Niels Schmitt, and Hans Ulrich Simon, Estimating the optimal margins of embeddings in Euclidean half spaces, Computational learning theory (Amsterdam, 2001) Lecture Notes in Comput. Sci., vol. 2111, Springer, Berlin, 2001, pp. 402–415. MR 2042049, DOI 10.1007/3-540-44581-1_{2}6
Michel Ledoux and Michel Talagrand, Probability in Banach spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 23, Springer-Verlag, Berlin, 1991. Isoperimetry and processes. MR 1102015, DOI 10.1007/978-3-642-20212-4
N. Linial, S. Mendelson, G. Schechtman, A. Shraibman, Complexity measures of sign matrices, Combinatorics, to appear.
Shahar Mendelson, Embedding with a Lipschitz function, Random Structures Algorithms 27 (2005), no. 1, 25–45. MR 2149294, DOI 10.1002/rsa.20054
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
Alain Pajor, Sous-espaces $l^n_1$ des espaces de Banach, Travaux en Cours [Works in Progress], vol. 16, Hermann, Paris, 1985 (French). With an introduction by Gilles Pisier. MR 903247
Gilles Pisier, The volume of convex bodies and Banach space geometry, Cambridge Tracts in Mathematics, vol. 94, Cambridge University Press, Cambridge, 1989. MR 1036275, DOI 10.1017/CBO9780511662454