Metric Approximation
An r-cover provides a nearby representative for every point in A.
The Approximation Question
Metric approximation asks how a set of representative points can stand in for an entire set. Given a set A, a radius r specifies how much distance is allowed between a point of A and its representative. Another set, written A′, supplies the representatives. The central question is whether every point of A can find a point of A′ no farther away than r.
The radius r controls the permitted error, while A′ controls which representative points are available.
Finding a Representative
A set A′ r-covers A when, for every point a in A, there is some point a′ in A′ such that ‖a − a′‖ ≤ r. The inequality uses the Euclidean metric.
The definition has two parts. First, the requirement applies to every point a in A. Second, the representative may depend on a: different points of A can be matched with different points of A′. The distance from each point to its chosen representative must satisfy the same radius bound r.
Checking an r-cover
Let A contain three points on a line: (0, 0), (1, 0), and (2, 0). Let A′ contain only (1, 0), and let r = 1. Does A′ 1-cover A?
Check the first point: The Euclidean distance from (0, 0) to (1, 0) is 1, which is no greater than r.
Check the middle point: The distance from (1, 0) to the representative (1, 0) is 0, which is no greater than r.
Check the last point: The Euclidean distance from (2, 0) to (1, 0) is 1, which is no greater than r.
Yes. Every point of A has a representative in A′ at Euclidean distance at most 1.
Counting the Smallest Cover
N(r, A) is the size of the smallest set that r-covers A. It measures how many representative points are needed to approximate every point of A within the chosen radius r.
The phrase smallest set is essential. A set A′ may r-cover A even when it contains more representatives than necessary. The covering number ignores those extra representatives and records the minimum possible number.
From a cover to a covering number
Use the previous set A = {(0, 0), (1, 0), (2, 0)} with r = 1. Determine N(r, A).
Exhibit a valid cover: The one-point set A′ = {(1, 0)} 1-covers A because every point of A is at Euclidean distance at most 1 from (1, 0).
Use the minimum requirement: A covering set cannot contain fewer than one representative point, because an empty set supplies no representative for any point of A.
Identify the minimum: A valid cover with one representative exists, and no valid cover can use zero representatives.
N(1, A) = 1 for this generated example.
Rescaling and Shifting Sets
Covering numbers have structural properties under two transformations of a set: multiplying the set by a positive scalar c and translating it by a vector a₀. For a set A contained in R^m, these operations produce a rescaled or shifted version of the original set. The corresponding cover can be studied alongside the original cover, allowing comparisons between the original and transformed sets.
When analyzing a transformed set, track both the set and its representatives. Do not discuss only the transformed points; the approximation question still depends on whether every transformed point has an appropriate representative within the relevant radius.
Transformed Distances
A coordinatewise Lipschitz condition is used when studying transformed sets. Its purpose is to control how corresponding points behave under a transformation: points are compared before the map and then compared again after the map. This kind of condition provides a way to relate the geometry of the original sets to the geometry of their transformed versions.
Common Reasoning Errors
Checking only some points of A
The definition requires a representative for every point of A.
Fix:
Verify the distance requirement point by point for the entire set A.Treating r as the number of representatives
The radius specifies the permitted distance; N(r, A) counts representatives.
Fix:
Keep the roles separate: r is the distance tolerance, while N(r, A) is the minimum representative count.Using any cover to define N(r, A)
N(r, A) is based on the smallest set that r-covers A.
Fix:
Compare valid covers and use the minimum number of representatives.Assuming a transformation removes the need to analyze representatives
The structural properties compare the cover of the original set with the cover of the transformed set.
Fix:
Transform and track the representative set as well as the original set.Inventing a precise coordinatewise Lipschitz formula
The provided material names the condition but does not state its exact formula.
Fix:
Describe its role as controlling corresponding distances, and use an exact formula only when it has been explicitly defined.
Practice Check
Let A = {(0, 0), (2, 0), (4, 0)} and let r = 2. Consider A′ = {(2, 0)}. Decide whether A′ r-covers A, then determine the value of N(r, A) for this generated example.
Hints
- Compute the Euclidean distance from each point of A to (2, 0).
- After finding one valid representative set, ask whether a set with zero representatives could cover A.
- Metric approximation replaces the demand to list or use every point of A with a representative set A′. The set A′ r-covers A when every a in A has an a′ in A′ satisfying ‖a − a′‖ ≤ r under the Euclidean metric. N(r, A) is the minimum size of such a representative set. Scaling by a positive scalar and translation by a vector are structural transformations used to compare covering numbers, while a coordinatewise Lipschitz condition is used to control corresponding points under transformations.
Key Takeaways
- An r-cover gives every point of A a representative in A′ at Euclidean distance at most r.
- The radius r determines the permitted approximation distance.
- N(r, A) counts the representatives in the smallest r-cover of A.
- Scaling by a positive scalar and translation by a vector are structural properties used when comparing covers of transformed sets.
- A coordinatewise Lipschitz condition provides distance control for corresponding points before and after a transformation.