Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Lipschitz representations of subsets of the cube

Author: Shahar Mendelson
Journal: Proc. Amer. Math. Soc. 135 (2007), 1455-1463
MSC (2000): Primary 46B07, 60D05
Published electronically: November 14, 2006
MathSciNet review: 2276655
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. S. Ben-David, N. Eiron, H.U. Simon, Limitations of learning via embeddings in Euclidean half spaces, Journal of Machine Learning Research 3, 441-461, 2002. MR 1984025 (2004f:68048)
  • 2. B. Bollobás, Extremal graph theory, Academic Press, 1978.MR 0506522 (80a:05120)
  • 3. J. Forster, N. Schmitt, and H.U. Simon, Estimating the optimal margins of embeddings in Euclidean halfspaces, in Proceedings of the 14th Annual Conference on Computational Learning Theory, 2001, LNCS volume 2111, 402-415. Springer, Berlin, 2001.MR 2042049
  • 4. M. Ledoux, M. Talagrand, Probability in Banach spaces, Springer, 1991.MR 1102015 (93c:60001)
  • 5. N. Linial, S. Mendelson, G. Schechtman, A. Shraibman, Complexity measures of sign matrices, Combinatorics, to appear.
  • 6. S. Mendelson, Embedding with a Lipschitz function, Random Structures and Algorithms, 27(1) 25-45, 2005. MR 2149294
  • 7. V.D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces, Lecture Notes in Mathematics 1200, Springer, 1986. MR 0856576 (87m:46038)
  • 8. A. Pajor, Sous espaces $ \ell_1^n$ des espaces de Banach, Hermann, Paris, 1985.MR 0903247 (88h:46028)
  • 9. G. Pisier, The volume of convex bodies and Banach space geometry, Cambridge University Press, 1989.MR 1036275 (91d:52005)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 46B07, 60D05

Retrieve articles in all journals with MSC (2000): 46B07, 60D05

Additional Information

Shahar Mendelson
Affiliation: Centre for Mathematics and its Applications, The Australian National University, Canberra, ACT 0200, Australia

Received by editor(s): April 29, 2005
Received by editor(s) in revised form: December 20, 2005
Published electronically: November 14, 2006
Additional Notes: The author was supported in part by an Australian Research council Discovery grant.
Communicated by: N. Tomczak-Jaegermann
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society