×

Weighted covering numbers of convex sets. (English) Zbl 1221.52026

The “classical” covering number \(N(K,T)\) for \(K,T \subset \mathbb{R}^d\) is the minimal number \(N\) over all possible coverings \(\bigcup_{i=1}^N(x_i+T) \supset K\) of \(K\) by \(T\). The authors generalize this notion in the following way: A sequence of \(N\) pairs \((x_i,w_i) \in K \times \mathbb{R}^+\) is called a weighted covering of \(K\) by \(T\) if for all \(x \in K\) holds \(\sum{w_i \mathbf{1}_{T+x_i}(x)} \geq 1\) where \(\mathbf{1}_A\) denotes the indicator function of \(A\). The infimal total weight \(\sum_1^Nw_i\) over all weighted coverings of \(K\) by \(T\) is called the weighted covering number \(N_w(K,T)\) of \(K\) by \(T\). Analogously, the \(T\)-separation number \(M(K,T)\) in \(K\) is generalized to the weighted \(T\)-separation number \(M_w(K,T)\).
The main results of the paper are as follows: For convex bodies \(K,T\) with symmetric \(T=-T\) holds \(N(K,2T)\leq N_w(K,T)\leq N(K,T)\) and \(N_w(K,T)=M_w(K,T)\).
Reviewer: Eike Hertel (Jena)

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces)
Full Text: DOI

References:

[1] Artstein, S.; Milman, V.; Szarek, S. J., Duality of metric entropy, Ann. Math., 159, 1-16 (2004) · Zbl 1072.52001
[2] Dantzig, George B.; Thapa, Mukund N., Linear Programming. 1. Introduction, Springer Ser. Oper. Res. (1997), Springer-Verlag: Springer-Verlag New York · Zbl 0883.90090
[3] Dudley, R. M., The sizes of compact subsets of Hilbert space and continuity of Gaussian processes, J. Funct. Anal., 1, 290-330 (1967) · Zbl 0188.20502
[4] Kuelbs, J.; Li, W. V., Metric entropy and the small ball problem for Gaussian measures, J. Funct. Anal., 116, 133-157 (1993) · Zbl 0799.46053
[5] Ledoux, M., Isoperimetry and Gaussian analysis, (Lectures on Probability Theory and Statistics. Lectures on Probability Theory and Statistics, Saint-Flour, 1994. Lectures on Probability Theory and Statistics. Lectures on Probability Theory and Statistics, Saint-Flour, 1994, Lecture Notes in Math., vol. 1648 (1996), Springer-Verlag: Springer-Verlag New York), 165-294 · Zbl 0874.60005
[6] Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 4, 383-390 (1975) · Zbl 0323.05127
[7] Pietsch, A., Theorie der Operatorenideale (Zusammenfassung) (1972), Friedrich-Schiller-Universität Jena · Zbl 0238.46067
[8] Pisier, G., The Volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Math., vol. 94 (1989), Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0698.46008
[9] O. Raz, M.Sc. Thesis, Tel Aviv University, 2011.; O. Raz, M.Sc. Thesis, Tel Aviv University, 2011.
[10] Scheinerman, Edward R.; Ulman, Daniel H., Fractional Graph Theory (2008), John Wiley & Sons
[11] Schütt, C., Entropy numbers of diagonal operators between symmetric Banach spaces, J. Approx. Theory, 40, 121-128 (1984) · Zbl 0497.41017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.