{{Short description|Number of balls of a given size needed to cover a given space}} {{distinguish|text=Winding number or degree of a continuous mapping, sometimes called "covering number" or "engulfing number"}}
In mathematics, a '''covering number''' is the number of balls of a given size needed to completely cover a given space, with possible overlaps between the balls. The covering number quantifies the size of a set and can be applied to general metric spaces. Two related concepts are the ''packing number'', the number of disjoint balls that fit in a space, and the ''metric entropy'', the number of points that fit in a space when constrained to lie at some fixed minimum distance apart.
== Definition ==
Let (''M'', ''d'') be a metric space, let ''K'' be a subset of ''M'', and let ''r'' be a positive real number. Let ''B''<sub>''r''</sub>(''x'') denote the closed ball of radius ''r'' centered at ''x''. A subset ''C'' of ''M'' is an ''r-external covering'' of ''K'' if: :<math>K \subseteq \bigcup_{x \in C} B_r(x)</math>. In other words, for every <math>y\in K</math> there exists <math>x\in C</math> such that <math>d(x,y)\leq r</math>.
If furthermore ''C'' is a subset of ''K'', then it is an ''r-internal covering''.
The '''external covering number''' of ''K'', denoted <math>N^{\text{ext}}_r(K)</math>, is the minimum cardinality of any external covering of ''K''. The '''internal covering number''', denoted <math>N^{\text{int}}_r(K)</math>, is the minimum cardinality of any internal covering.
A subset ''P'' of ''K'' is a ''packing'' if <math>P \subseteq K</math> and the set <math>\{B_r(x)\}_{x \in P}</math> is pairwise disjoint. The '''packing number''' of ''K'', denoted <math>N^{\text{pack}}_r(K)</math>, is the maximum cardinality of any packing of ''K''.
A subset ''S'' of ''K'' is ''r''-''separated'' if each pair of points ''x'' and ''y'' in ''S'' satisfies ''d''(''x'', ''y'') ≥ ''r''. The '''metric entropy''' of ''K'', denoted <math>N^{\text{met}}_r(K)</math>, is the maximum cardinality of any ''r''-separated subset of ''K''.
== Examples == {{ordered list | The metric space is the real line <math>\mathbb{R}</math>. <math>K\subset \mathbb{R}</math> is a set of real numbers whose absolute value is at most <math>k</math>. Then, there is an external covering of <math display="inline">\left\lceil \frac{2k}{r} \right\rceil</math> intervals of length <math>r</math>, covering the interval <math>[-k, k]</math>. Hence: :<math>N^{\text{ext}}_r(K) \leq \frac{2 k}{r}</math> | The metric space is the Euclidean space <math>\mathbb{R}^m</math> with the Euclidean metric. <math>K\subset \mathbb{R}^m</math> is a set of vectors whose length (norm) is at most <math>k</math>. If <math>K</math> lies in a ''d''-dimensional subspace of <math>\mathbb{R}^m</math>, then:<ref name=book14>{{Cite Shai Shai 2014}}</ref>{{rp|337}} : <math>N^{\text{ext}}_r(K) \leq \left(\frac{2 k \sqrt{d}}{r}\right)^d</math>. | The metric space is the space of real-valued functions, with the ℓ-infinity metric. The covering number <math>N^{\text{int}}_r(K)</math> is the smallest number <math>k</math> such that there exist <math>h_1,\ldots,h_k \in K</math> such that, for all <math>h\in K</math> there exists <math>i\in\{1,\ldots,k\}</math> such that the supremum distance between <math>h</math> and <math>h_i</math> is at most <math>r</math>. The above bound is not relevant since the space is <math>\infty</math>-dimensional. However, when <math>K</math> is a compact set, every covering of it has a finite sub-covering, so <math>N^{\text{int}}_r(K)</math> is finite.<ref name=book12>{{Cite Mehryar Afshin Ameet 2012}}</ref>{{rp|61}} }}
== Properties == {{ordered list | The internal and external covering numbers, the packing number, and the metric entropy are all closely related. The following chain of inequalities holds for any subset ''K'' of a metric space and any positive real number ''r''.<ref>{{cite web|last1=Tao|first1=Terence|title=Metric entropy analogues of sum set theory|date=20 March 2014 |url=http://terrytao.wordpress.com/2014/03/19/metric-entropy-analogues-of-sum-set-theory/|accessdate=2 June 2014}}</ref>
: <math>N^{\text{met}}_{2 r}(K) \leq N^{\text{pack}}_r(K) \leq N^{\text{ext}}_r(K) \leq N^{\text{int}}_r(K) \leq N^{\text{met}}_r(K)</math> | Each function except the internal covering number is non-increasing in ''r'' and non-decreasing in ''K''. The internal covering number is monotone in ''r'' but not necessarily in ''K''. }}
The following properties relate to covering numbers in the standard Euclidean space, <math>\mathbb{R}^m</math>:<ref name=book14/>{{rp|338}} {{ordered list | start = 3 | If all vectors in <math>K</math> are translated by a constant vector <math>k_0\in \mathbb{R}^m</math>, then the covering number does not change. | If all vectors in <math>K</math> are multiplied by a scalar <math>k \in \mathbb{R}</math>, then: : for all <math>r</math>: <math>N^{\text{ext}}_{|k|\cdot r}(k\cdot K) = N^{\text{ext}}_{r}(K)</math> | If all vectors in <math>K</math> are operated by a Lipschitz function <math>\phi</math> with Lipschitz constant <math>k</math>, then: : for all <math>r</math>: <math>N^{\text{ext}}_{|k|\cdot r}(\phi\circ K) \leq N^{\text{ext}}_{r}(K)</math> }}
== Application to machine learning == Let <math>K</math> be a space of real-valued functions, with the ℓ-infinity metric (see example 3 above). Suppose all functions in <math>K</math> are bounded by a real constant <math>M</math>. Then, the covering number can be used to bound the generalization error of learning functions from <math>K</math>, relative to the squared loss:<ref name=book12/>{{rp|61}} : <math> \operatorname{Prob}\left[ \sup_{h\in K} \big\vert\text{GeneralizationError}(h) - \text{EmpiricalError}(h)\big\vert \geq \epsilon \right] \leq N^\text{int}_r (K)\, 2\exp{-m\epsilon^2 \over 2M^4} </math>
where <math>r = {\epsilon \over 8M}</math> and <math>m</math> is the number of samples.
== See also == * Polygon covering * Kissing number
== References == {{reflist}}
Category:Topology Category:Metric geometry