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

Artstein-Avidan, S.; Friedland, O.; Milman, V.

doi:10.1090/S0002-9939-05-08144-X

Geometric applications of Chernoff-type estimates and a ZigZag approximation for balls
HTML articles powered by AMS MathViewer

by S. Artstein-Avidan, O. Friedland and V. Milman

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

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

Published electronically: December 14, 2005

PDF | Request permission

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

S. Artstein-Avidan, O. Friedland, V. Milman, Geometric Applications of Chernoff-type Estimates, to appear in Springer Lecture Notes, GAFA Seminar, 2004–2005.
Andrew R. Barron, Universal approximation bounds for superpositions of a sigmoidal function, IEEE Trans. Inform. Theory 39 (1993), no. 3, 930–945. MR 1237720, DOI 10.1109/18.256500
Gerald H. L. Cheang and Andrew R. Barron, A better approximation for balls, J. Approx. Theory 104 (2000), no. 2, 183–203. MR 1761898, DOI 10.1006/jath.1999.3441
G. Cybenko, Approximation by superpositions of sigmoidal functions, Proc. of the 1994 IEEE-IMS Workshop on Info. Theory and Stat. (1994).
Torben Hagerup and Christine Rüb, A guided tour of Chernoff bounds, Inform. Process. Lett. 33 (1990), no. 6, 305–308. MR 1045520, DOI 10.1016/0020-0190(90)90214-I
K. Hornik, M.B. Stinchcombe and H. White, Multi-layer feedforward networks are universal approximators, Neural Networks 2 (1988), 359–366.
W. B. Johnson and G. Schechtman, Very tight embeddings of subspaces of $L_p$, $1\leq p<2$, into $l^n_p$, Geom. Funct. Anal. 13 (2003), no. 4, 845–851. MR 2006559, DOI 10.1007/s00039-003-0432-9
A.E. Litvak, A. Pajor, M. Rudelson, and N. Tomczak-Jaegermann, Smallest singular value of random matrices and geometry of random polytopes, preprint.
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, DOI 10.1016/j.crma.2004.04.019
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, DOI 10.4064/sm159-2-6
Gideon Schechtman, Special orthogonal splittings of $L^{2k}_1$, Israel J. Math. 139 (2004), 337–347. MR 2041797, DOI 10.1007/BF02787555
Gideon Schechtman, Random embeddings of Euclidean spaces in sequence spaces, Israel J. Math. 40 (1981), no. 2, 187–192. MR 634905, DOI 10.1007/BF02761909