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)

 
 

 

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 $ 1$ in $ \mathbb{R}^n$ can be approximated up to $ \varepsilon>0$, in the Hausdorff distance, by a set defined by $ N = C(\varepsilon)n$ linear inequalities. We call this set a ZigZag set, and it is defined to be all points in space satisfying $ 50%$ or more of the inequalities. The constant we get is $ C(\varepsilon) = C \ln (1/\varepsilon)/\varepsilon^2$, where $ C$ is some universal constant. This should be compared with the result of Barron and Cheang (2000), who obtained $ N = Cn^2/\varepsilon^2$. 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.


References [Enhancements On Off] (What's this?)

  • [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 $ L_p$, $ 1 \le p < 2$, into $ \ell_p^n$, 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 $ L\sp {2k}\sb 1$, 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)

Similar Articles

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

American Mathematical Society