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

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

Published electronically:
December 14, 2005

MathSciNet review:
2204286

Full-text PDF

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]**A. R. Barron,*Universal approximation bounds for superpositions of a sigmoidal function*, IEEE Trans. Inform. Theory 39 (1993), 930-945. MR**1237720 (94h:92001)****[CB]**G. Cheang and A. Barron,*A better approximation for balls*, J. Approx. Theory 104 (2000) no. 2, 183-203. MR**1761898 (2001d:41018)****[C]**G. Cybenko,*Approximation by superpositions of sigmoidal functions*, Proc. of the 1994 IEEE-IMS Workshop on Info. Theory and Stat. (1994).**[HR]**T. Hagerup and C. Rüb,*A guided tour of Chernoff bounds*, Inform. Process. Lett. 33 (1990) no. 6, 305-308. MR**1045520 (91h:60022)****[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 , , into*, Geom. and Funct. Anal. (GAFA), 13, no. 4 (2003), 845-851. MR**2006559 (2004h:46014)****[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]**A.E. Litvak, A. Pajor, M. Rudelson, N. Tomczak-Jaegermann, and R. Vershynin,*Random Euclidean embeddings in spaces of bounded volume ratio*, C. R. Math. Acad. Sci. Paris 339 (2004), no. 1, 33-38. MR**2075229****[MP]**V.D. Milman and A. Pajor,*Regularization of star bodies by random hyperplane cut off*, Studia Methematica 159 (2) (2003), 247-261. MR**2052221 (2005e:52009)****[S1]**G. Schechtman,*Special orthogonal splittings of*, Israel J. Math. 139 (2004), 337-347. MR**2041797 (2005a:46036)****[S2]**G. Schechtman,*Random embeddings of euclidean spaces in sequence spaces*, Israel Journal of Mathematics 40, no. 2 (1981), 187-192. MR**0634905 (83a:46032)**

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:
https://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