|
Lipschitz representations of subsets of the cube
Author(s):
Shahar
Mendelson
Journal:
Proc. Amer. Math. Soc.
135
(2007),
1455-1463.
MSC (2000):
Primary 46B07, 60D05
Posted:
November 14, 2006
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
We show that for any class of uniformly bounded functions  with a reasonable combinatorial dimension, the vast majority of small subsets of the  -dimensional combinatorial cube cannot be represented as a Lipschitz image of a subset of  , unless the Lipschitz constant is very large. We apply this result to the case when  consists of linear functionals of norm at most one on a Hilbert space.
References:
-
- 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
 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
Email:
shahar.mendelson@anu.edu.au
DOI:
10.1090/S0002-9939-06-08620-5
PII:
S 0002-9939(06)08620-5
Received by editor(s):
April 29, 2005
Received by editor(s) in revised form:
December 20, 2005
Posted:
November 14, 2006
Additional Notes:
The author was supported in part by an Australian Research council Discovery grant.
Communicated by:
N. Tomczak-Jaegermann
Copyright of article:
Copyright
2006,
American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.
|
Comments: webmaster@ams.org