Metric Approximation
Metric approximation asks how a set of representative points can stand in for an entire set.
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?
- 1Check the first point
The Euclidean distance from (0, 0) to (1, 0) is 1, which is no greater than r.
- 2Check the middle point
The distance from (1, 0) to the representative (1, 0) is 0, which is no greater than r.
- 3Check 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).
- 1Exhibit 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).
- 2Use 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.
- 3Identify 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 Rm, 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
Common mistake Checking only some points of A
What it looks likeA′ is close to several visible points of A, so it is declared to be an r-cover.
Why it failsThe definition requires a representative for every point of A.
Do this insteadVerify the distance requirement point by point for the entire set A.
Common mistake Treating r as the number of representatives
What it looks likeA larger radius is interpreted as requiring more representative points.
Why it failsThe radius specifies the permitted distance; N(r, A) counts representatives.
Do this insteadKeep the roles separate: r is the distance tolerance, while N(r, A) is the minimum representative count.
Common mistake Using any cover to define N(r, A)
What it looks likeA′ has five representatives, so N(r, A) is reported as five even though a two-point cover exists.
Why it failsN(r, A) is based on the smallest set that r-covers A.
Do this insteadCompare valid covers and use the minimum number of representatives.
Common mistake Assuming a transformation removes the need to analyze representatives
What it looks likeAfter scaling or translating A, the transformed set is discussed without considering its corresponding cover.
Why it failsThe structural properties compare the cover of the original set with the cover of the transformed set.
Do this insteadTransform and track the representative set as well as the original set.
Common mistake Inventing a precise coordinatewise Lipschitz formula
What it looks likeA specific constant or inequality is asserted even though it was not supplied.
Why it failsThe provided material names the condition but does not state its exact formula.
Do this insteadDescribe 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.
- 1Metric 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.