# Covering number

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Covering_number
> Markdown URL: https://mediated.wiki/source/Covering_number.md
> Source: https://en.wikipedia.org/wiki/Covering_number
> Source revision: 1326919535
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Number of balls of a given size needed to cover a given space}}
{{distinguish|text=[Winding number](/source/Winding_number) or [degree of a continuous mapping](/source/degree_of_a_continuous_mapping), sometimes called "covering number" or "engulfing number"}}

In [mathematics](/source/mathematics), a '''covering number''' is the number of [ball](/source/ball_(mathematics))s 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](/source/Metric_space). 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](/source/metric_space), let ''K'' be a subset of ''M'', and let ''r'' be a positive [real number](/source/real_number). Let ''B''<sub>''r''</sub>(''x'') denote the closed [ball](/source/Ball_(mathematics)) 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](/source/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](/source/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](/source/Euclidean_space) <math>\mathbb{R}^m</math> with the [Euclidean metric](/source/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](/source/l-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](/source/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](/source/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](/source/Lipschitz_function) <math>\phi</math> with [Lipschitz constant](/source/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](/source/l-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](/source/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](/source/Polygon_covering)
* [Kissing number](/source/Kissing_number)

== References ==
{{reflist}}

Category:Topology
Category:Metric geometry

---
Adapted from the Wikipedia article [Covering number](https://en.wikipedia.org/wiki/Covering_number) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Covering_number?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.