We will be working in the column space of a matrix A∈Rn×dA \in \mathbb{R}^{n \times d}. Without loss of generality, we will assume that AA has orthonormal columns; if it doesn’t, we can always find an orthonormal basis for its column space by considering its SVD, A=UΣV∗A=U\Sigma V^\ast, and redefining A:=UA:=U. That is enough because the set {Ax  ∣  x∈Rd}\{ Ax \;|\; x \in \mathbb{R}^d\} is the same as the set {Uz  ∣  z∈Rρ}\{ Uz \;|\; z \in \mathbb{R}^\rho \} where ρ\rho is the rank of AA.

Definition: Define the set S={y  ∣  y=Ax,  ∥y∥2=1}\mathcal{S} = \{ y \;|\; y=Ax, \; \lVert y \rVert_2 = 1 \}. An ϵ\epsilon-net is a subset N⊂S\mathcal{N} \subset \mathcal{S} such that, for every y∈Sy \in \mathcal{S}, there exists a w∈Nw \in \mathcal{N}such that ∥y−w∥2≤ϵ\lVert y - w \rVert_2 \leq \epsilon.

A finite set can cover every direction Eight net points lie on a unit circle. Balls of radius epsilon around them cover the circle. A point y on the circle is within epsilon of a net point w. The drawing uses epsilon equal to 0.6, and is a two-dimensional example. A finite set can cover every direction y w infinitely many directions finitely many representatives for every y on the sphere, find a w in the net ||y − w|| ≤ ε Only the sphere needs to be covered — not the whole surrounding ball.
A two-dimensional example: the colored centers form a finite net on the unit circle. Every point on that circle is within ε of a center. The covering balls extend off the circle; their centers remain on it. View largerScroll sideways for the full sketch.

Existence

Lemma: For ϵ∈(0,1)\epsilon \in (0, 1), there exists an ϵ\epsilon-net N\mathcal{N} for the set S\mathcal{S} (defined above) whose size is at most (1+2/ϵ)d(1 + 2/\epsilon)^d.

Proof: Let’s consider the unit sphere in Rd:Sd−1\mathbb{R}^d: \mathbb{S}^{d-1}. Instead of finding a net for S\mathcal{S}, we will argue by finding a net for Sd−1\mathbb{S}^{d - 1}. That’s because AA provides an isometry when operating on the unit sphere, so that a net for Sd−1\mathbb{S}^{d - 1} gives us a net for the image of Sd−1\mathbb{S}^{d - 1} under AA.

Finding a net over the unit sphere is trivial. We can choose a maximal set N′\mathcal{N}^\prime such that no two points in the set are within distance ϵ\epsilon from each other. This means that balls of radius ϵ/2\epsilon/2 centered at points in N′\mathcal{N}^\prime are disjoint. These balls all fit in the ball with radius (1+ϵ/2)(1 + \epsilon/2) centered at the origin. The volume of this enlarged ball is (1+ϵ/2)d/(ϵ/2)d(1 + \epsilon/2)^d / (\epsilon/2)^d times larger than the small balls. As such, there can be at most (1+2/ϵ)d(1 + 2/\epsilon)^d small balls, implying that ∣N′∣≤(1+2/ϵ)d\lvert \mathcal{N}^\prime \rvert \leq (1 + 2/\epsilon)^d. [This is the covering number of the unit sphere, which is a compact set.]

The volume argument: pack small balls Separated net points on the unit sphere have disjoint balls of radius epsilon over two. Each small ball lies inside the ball of radius one plus epsilon over two. Comparing volumes bounds the number of net points by one plus two over epsilon to the power d. The volume argument: pack small balls 1 + ε/2 radius ε/2 disjoint small balls all inside one larger ball |N| · (ε/2)d ≤ (1 + ε/2)d |N| ≤ (1 + 2/ε)d Maximal separation also forces the covering property. The same unit-ball volume factor appears on both sides, so it cancels.
For a maximal ε-separated set, the radius-ε/2 balls are disjoint and fit inside a radius-(1 + ε/2) ball. Volume scales as radius to the power d, giving |N| ≤ (1 + 2/ε)ᵈ. View largerScroll sideways for the full sketch.

Now let N={y  ∣  y=Ax,  x∈N′}\mathcal{N} = \{ y \;|\; y = Ax, \; x \in \mathcal{N}^\prime \}. We can show by contradiction that, for any y∈Sy \in \mathcal{S} there must exist a point ww in N\mathcal{N} such that ∥y−w∥2≤ϵ\lVert y - w \rVert_2 \leq \epsilon.\mathbb{} Suppose there exists no such ww for some y=Axy=Ax for some x∈Sd−1x \in \mathbb{S}^{d - 1}. That implies that, there exists no point vv in N′\mathcal{N}^\prime for which ∥x−v∥2≤ϵ\lVert x - v \rVert_2 \leq \epsilon. But that contradicts our construction of N′\mathcal{N}^\prime.