Existence of Optimal Quantizers on Compact Support

Why Existence Needs an Argument

For a fixed number of centers, clustering seeks a codebook with small average squared distance from the distribution to its nearest center. It is tempting to say that a best codebook must exist because one can keep improving a proposed one. But an infimum need not be attained: a sequence of codebooks can approach the best possible risk while its centers escape to infinity or approach a configuration excluded from the parameter space. An existence proof therefore needs both a suitably bounded search region and continuity of the risk on that region.

Compact support provides the needed bounded region. More precisely, centers can be restricted to the convex hull of the support, which is compact in finite-dimensional Euclidean space. Continuity then ensures that the risk reaches its minimum there. The restriction is useful even when the support itself is not convex: a good center may lie in a gap between supported values.

Definition: Let $X$ be a random vector in $\mathbb{R}^d$, and suppose $P(X\in C)=1$ for a nonempty compact set $C\subset\mathbb{R}^d$. For a positive integer $K$, a K-center codebook is an ordered tuple $A=(a_1,\ldots,a_K)$ of points in $\mathbb{R}^d$. Its squared-distance quantization risk is $$ R(A)=E\left[\min_{1\leq j\leq K}\|X-a_j\|^2\right]. $$ The standard formulation allows repeated centers; equivalently, a codebook may have fewer than $K$ distinct centers.

The minimization is over the entire codebook, not over a particular assignment of observations to centers. For each realized $X$, its contribution is the squared distance to the closest center. Because $X$ lies in a bounded set almost surely, the risk is finite for every finite codebook. No density, absence of atoms, or uniqueness of a minimizer is required.

Projection Onto the Convex Hull

Write $H=\operatorname{conv}(C)$, the convex hull of the support set. This is the smallest convex set containing $C$. Since $C$ is compact and the ambient space is finite-dimensional, $H$ is also compact. One way to see this is Carathéodory’s theorem: every point in $H$ is a convex combination of at most $d+1$ points of $C$. Thus $H$ is the image of the compact set consisting of $d+1$ points of $C$ and their weights in the closed probability simplex, under the continuous map that forms the weighted sum.

The geometric fact behind the restriction is that projecting a proposed center onto a closed convex set cannot increase its distance to any point in that set. Here is the needed fact, including its justification.

Projection lemma: If $H\subset\mathbb{R}^d$ is nonempty, closed, and convex, then for every $a\in\mathbb{R}^d$ there is a point $p\in H$ such that $$ \|x-p\|\leq \|x-a\| \qquad\text{for every }x\in H. $$

To prove the lemma, choose $p\in H$ minimizing $\|a-p\|$. Such a point exists: a sequence in $H$ whose distances to $a$ approach the infimum is bounded, so it has a convergent subsequence, and its limit belongs to $H$ because $H$ is closed. For any $x\in H$, convexity gives $p+t(x-p)\in H$ for $0\leq t\leq1$. Minimality of $p$ implies

\|a-p-t(x-p)\|^2\geq\|a-p\|^2.

Expanding, dividing by $t>0$, and letting $t$ decrease to zero gives $(a-p)\cdot(x-p)\leq0$. Now expand the squared distance from $a$ to $x$:

\|a-x\|^2 =\|a-p\|^2+\|p-x\|^2+2(a-p)\cdot(p-x) \geq \|p-x\|^2.

The last inequality follows from $(a-p)\cdot(p-x)\geq0$. This proves the lemma. In finite-dimensional Euclidean space, $p$ is the metric projection of $a$ onto $H$.

Worked Example: A Center Outside the Support

Suppose $P(X=0)=3/4$ and $P(X=2)=1/4$, with $K=1$. The support is $\{0,2\}$, and its convex hull is $[0,2]$. For a proposed center $c$, the risk is

R(c)=\frac34c^2+\frac14(2-c)^2 =c^2-c+1 =\left(c-\frac12\right)^2+\frac34.

The minimum is $3/4$, attained at $c=1/2$, which is in the convex hull but is not a supported value of $X$. Restricting centers to the support itself would therefore exclude this minimizer. By contrast, a proposed center $c=3$ has risk $7$; projecting it to $2$ reduces the risk to $3$. Projection is a risk-reducing restriction, not a claim that an optimal center must itself be an observed or supported value.

Apply the projection lemma separately to each center of an unrestricted codebook $A=(a_1,\ldots,a_K)$, and denote the projected codebook by $A'=(p_1,\ldots,p_K)$, where $p_j$ is the projection of $a_j$ onto $H$. For every $x\in C\subset H$, each individual distance satisfies $\|x-p_j\|\leq\|x-a_j\|$. Taking the minimum over $j$, squaring, and then taking expectation shows that $R(A')\leq R(A)$. Thus restricting every center to $H$ cannot worsen the best achievable risk.

Continuity of Risk on the Restricted Space

It remains to show that risk varies continuously with the centers in $H$. This step is essential: compactness alone does not guarantee that a function attains its infimum. Let $D=\sup_{u,v\in H}\|u-v\|$, the finite diameter of $H$. For two codebooks $A=(a_1,\ldots,a_K)$ and $B=(b_1,\ldots,b_K)$ in $H^K$, set $\delta=\max_j\|a_j-b_j\|$. Every $x\in C$ and every center in either codebook lie in $H$, so all the distances in the following bound are at most $D$:

\left|\|x-a_j\|^2-\|x-b_j\|^2\right| \leq \|a_j-b_j\|\bigl(\|x-a_j\|+\|x-b_j\|\bigr) \leq 2D\delta.

For any two finite lists of real numbers $(u_j)$ and $(v_j)$, $\left|\min_j u_j-\min_j v_j\right|\leq\max_j|u_j-v_j|$. Applying this inequality to the squared distances gives a bound on the difference of the two nearest-center losses for every $x\in C$. Taking expectations yields

|R(A)-R(B)|\leq 2D\delta.

In particular, if $A$ approaches $B$ coordinate by coordinate, its risk approaches $R(B)$. If $H$ is a singleton, then $D=0$, and the risk on $H^K$ is constant, so continuity holds in that case as well. The random loss is measurable because it is the minimum of finitely many continuous functions of $X$; it is bounded on $C$ for codebooks in $H^K$, so the expectations used here are well-defined.

Existence Theorem

Theorem: If $P(X\in C)=1$ for a nonempty compact set $C\subset\mathbb{R}^d$, then for every positive integer $K$, there is a K-center codebook $A^*\in H^K$, with $H=\operatorname{conv}(C)$, that minimizes squared-distance quantization risk over all codebooks in $(\mathbb{R}^d)^K$.

Proof. The set $H$ is compact, so the finite product $H^K$ is compact. The continuity bound above shows that $R$ is continuous on $H^K$. The extreme value theorem therefore gives a codebook $A^*\in H^K$ minimizing $R$ over $H^K$. For any unrestricted codebook $A\in(\mathbb{R}^d)^K$, project each center onto $H$ to obtain a codebook $A'\in H^K$. The projection argument gives $R(A')\leq R(A)$. By the minimizing property of $A^*$, $R(A^*)\leq R(A')$. Consequently, $R(A^*)\leq R(A)$ for every unrestricted codebook $A$, which proves global attainment. $\square$

Worked Example: Three Equally Likely Points and Two Centers

Let $X$ take the values $0,2,4$, each with probability $1/3$, and let $K=2$. The support and its convex hull are $\{0,2,4\}$ and $[0,4]$, respectively. The theorem guarantees a minimizing pair of centers in $[0,4]$. In this example, its optimal risk can also be computed directly.

Assign each of the three values to a nearest center, resolving any ties arbitrarily. With only two centers, at least two of the three values are assigned to the same center, say $c$. Their separation is at least $2$. For any two real values $x,y$,

(x-c)^2+(y-c)^2 =2\left(c-\frac{x+y}{2}\right)^2+\frac{(x-y)^2}{2} \geq\frac{(x-y)^2}{2}.

Thus the two assigned values contribute at least $2$ to the unweighted sum of squared losses. The third loss is nonnegative, so the risk, which is that sum divided by $3$, is at least $2/3$. The codebook $(0,3)$ has squared losses $0,1,1$ at $0,2,4$, respectively, and hence risk $2/3$. It attains the lower bound and is optimal.

Worked Example: A Continuous Distribution on an Interval

Let $X$ be uniform on $[0,1]$ and take $K=1$. For any real-valued center $c$, integration gives

R(c)=\int_0^1(x-c)^2\,dx =\frac13-c+c^2 =\left(c-\frac12\right)^2+\frac1{12}.

The minimum is $1/12$, attained at $c=1/2$, inside the support’s convex hull. A center outside that interval can be improved by projection: for example, $c=-1$ has risk $\int_0^1(x+1)^2\,dx=7/3$, while its projection $0$ has risk $\int_0^1x^2\,dx=1/3$. This example also shows that compact support need not mean a finite or discrete distribution.

What the Result Does—and Does Not—Say

The theorem guarantees at least one global minimizer, but it does not claim that the minimizer is unique. Different codebooks can have the same risk, and permutations of a codebook’s entries never change its risk. Nor does the theorem provide an algorithm for finding a minimizer or establish that a particular numerical procedure will find one. Its conclusion is about existence and a safe compact search region.

A frequent mistake is to reason that compact support allows centers to be restricted to the support itself. The projection argument supports a different, precise conclusion: centers may be restricted to the convex hull of the support. In the two-point example above, the optimal center lies between the supported values. The convex hull is the appropriate geometric region because it is convex and contains every possible value of $X$, allowing the distance-reducing projection argument.

Another pitfall is to require exactly $K$ distinct centers without qualification. The standard codebook space consists of $K$-tuples and permits repetitions. If distinctness is imposed, the allowed set need not be closed: distinct centers can converge to a repeated-center configuration excluded from that set. Existence under that different constraint does not follow from this theorem. Allowing repetitions gives a compact parameter space $H^K$ and the conventional “at most $K$ effective centers” interpretation.

Key takeaway: Compact support places every possible observation in a compact convex hull. Projecting centers into that hull cannot increase nearest-center squared-distance risk, and the risk is continuous on the compact space of restricted codebooks. The extreme value theorem then guarantees an optimal codebook.

Check Your Understanding

Use the definitions and arguments above to answer these questions.

Why does the projection argument require the set containing the observations to be convex?
What inequality bounds the change in risk when two codebooks in $H^K$ are close?
For the distribution with equal mass at $0,2,4$ and $K=2$, why must some pair of support values share an assigned center?
Why does this theorem not imply that an optimal center must belong to the support itself?
What feature of the usual codebook definition helps make the restricted parameter space compact?