Geometric applications of Chernoff-type estimates and a ZigZag approximation for balls

Authors:
S. Artstein-Avidan, O. Friedland and V. Milman

Journal:
Proc. Amer. Math. Soc. **134** (2006), 1735-1742

MSC (2000):
Primary 46B07; Secondary 60D05, 46B09

Published electronically:
December 14, 2005

MathSciNet review:
2204286

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we show that the euclidean ball of radius in can be approximated up to , in the Hausdorff distance, by a set defined by linear inequalities. We call this set a ZigZag set, and it is defined to be all points in space satisfying or more of the inequalities. The constant we get is , where is some universal constant. This should be compared with the result of Barron and Cheang (2000), who obtained . The main ingredient in our proof is the use of Chernoff's inequality in a geometric context. After proving the theorem, we describe several other results which can be obtained using similar methods.

**[AFM]**S. Artstein-Avidan, O. Friedland, V. Milman,*Geometric Applications of Chernoff-type Estimates*, to appear in Springer Lecture Notes, GAFA Seminar, 2004-2005.**[B]**Andrew R. Barron,*Universal approximation bounds for superpositions of a sigmoidal function*, IEEE Trans. Inform. Theory**39**(1993), no. 3, 930–945. MR**1237720**, 10.1109/18.256500**[CB]**Gerald H. L. Cheang and Andrew R. Barron,*A better approximation for balls*, J. Approx. Theory**104**(2000), no. 2, 183–203. MR**1761898**, 10.1006/jath.1999.3441**[C]**G. Cybenko,*Approximation by superpositions of sigmoidal functions*, Proc. of the 1994 IEEE-IMS Workshop on Info. Theory and Stat. (1994).**[HR]**Torben Hagerup and Christine Rüb,*A guided tour of Chernoff bounds*, Inform. Process. Lett.**33**(1990), no. 6, 305–308. MR**1045520**, 10.1016/0020-0190(90)90214-I**[HSW]**K. Hornik, M.B. Stinchcombe and H. White,*Multi-layer feedforward networks are universal approximators*, Neural Networks 2 (1988), 359-366.**[JS]**W. B. Johnson and G. Schechtman,*Very tight embeddings of subspaces of 𝐿_{𝑝}, 1≤𝑝<2, into 𝑙ⁿ_{𝑝}*, Geom. Funct. Anal.**13**(2003), no. 4, 845–851. MR**2006559**, 10.1007/s00039-003-0432-9**[LPRT]**A.E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann,*Smallest singular value of random matrices and geometry of random polytopes*, preprint.**[LPRTV]**Alexander Litvak, Alain Pajor, Mark Rudelson, Nicole Tomczak-Jaegermann, and Roman Vershynin,*Random Euclidean embeddings in spaces of bounded volume ratio*, C. R. Math. Acad. Sci. Paris**339**(2004), no. 1, 33–38 (English, with English and French summaries). MR**2075229**, 10.1016/j.crma.2004.04.019**[MP]**V. D. Milman and A. Pajor,*Regularization of star bodies by random hyperplane cut off*, Studia Math.**159**(2003), no. 2, 247–261. Dedicated to Professor Aleksander Pełczyński on the occasion of his 70th birthday (Polish). MR**2052221**, 10.4064/sm159-2-6**[S1]**Gideon Schechtman,*Special orthogonal splittings of 𝐿^{2𝑘}₁*, Israel J. Math.**139**(2004), 337–347. MR**2041797**, 10.1007/BF02787555**[S2]**Gideon Schechtman,*Random embeddings of Euclidean spaces in sequence spaces*, Israel J. Math.**40**(1981), no. 2, 187–192. MR**634905**, 10.1007/BF02761909

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

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

Additional Information

**S. Artstein-Avidan**

Affiliation:
Department of Mathematics, Princeton University, Fine Hall, Washington Road, Princeton, New Jersey 08544-1000 – and – School of Mathematics, Institute for Advanced Study, 1 Einstein Drive, Princeton, New Jersey 08540

Email:
artstein@princeton.edu

**O. Friedland**

Affiliation:
School of Mathematical Science, Tel Aviv University, Ramat Aviv, Tel Aviv, 69978, Israel

Email:
omerfrie@post.tau.ac.il

**V. Milman**

Affiliation:
School of Mathematical Science, Tel Aviv University, Ramat Aviv, Tel Aviv, 69978, Israel

Email:
milman@post.tau.ac.il

DOI:
http://dx.doi.org/10.1090/S0002-9939-05-08144-X

Received by editor(s):
October 26, 2004

Received by editor(s) in revised form:
January 18, 2005

Published electronically:
December 14, 2005

Additional Notes:
This research was partially supported by BSF grant 2002-006 and by FP6 Marie Curie Actions “PHD”

Communicated by:
N. Tomczak-Jaegermann

Article copyright:
© Copyright 2005
American Mathematical Society