In mathematics, a covering number is the number of spherical balls of a given size needed to completely cover a given space, with possible overlaps. 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 be a metric space, let K be a subset of M, and let r be a positive real number. Let Br denote the ball of radius r centered at x. A subset C of M is an r-external covering of K if: In other words, for every there existssuch that. If furthermore C is a subset of K, then it is an r-internal covering. The external covering number of K, denoted, is the minimum cardinality of any external covering of K. The internal covering number, denoted, is the minimum cardinality of any internal covering. A subset P of K is a packing if and the set is pairwise disjoint. The packing number of K, denoted, 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 ≥ r. The metric entropy of K, denoted, is the maximum cardinality of any r-separated subset of K.
Examples
1. The metric space is the real line. is a set of real numbers whose absolute value is at most. Then, there is an external covering of intervals of length, covering the interval. Hence: 2. The metric space is the Euclidean space with the Euclidean metric. is a set of vectors whose length is at most. If lies in a d-dimensional subspace of, then: 3. The metric space is the space of real-valued functions, with the l-infinity metric. The covering number is the smallest number such that, there exist such that, for all there exists such that the supremum distance between and is at most. The above bound is not relevant since the space is -dimensional. However, when is a compact set, every covering of it has a finite sub-covering, so is finite.
Properties
1. 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 numberr. 2. 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 : 3. If all vectors in are translated by a constant vector, then the covering number does not change. 4. If all vectors in are multiplied by a scalar, then: 5. If all vectors in are operated by a Lipschitz function with Lipschitz constant, then:
Let be a space of real-valued functions, with the l-infinity metric. Suppose all functions in are bounded by a real constant. Then, the covering number can be used to bound the generalization error of learning functions from, relative to the squared loss:
