K-Medians and Alternative Quantization Distortions

Two Distortions, Two Notions of a Representative

A quantizer represents each observation by its nearest center. The rule assigning observations to centers is the same whether distance is squared or left unsquared: squaring is increasing on nonnegative distances. But the representative that minimizes the loss within a fixed cell can change. Squared distance favors the conditional mean; Euclidean distance leads to a geometric median.

Let \(X\) be a random vector in \(\mathbb{R}^d\), and let a codebook be \(c=(c_1,\ldots,c_K)\), with centers in a specified compact set \(C\subset\mathbb{R}^d\). The two population risks considered here are

The subscripts indicate the power of the distance in the loss. The corresponding empirical risks for independent observations \(X_1,\ldots,X_n\) are obtained by replacing the expectation with the sample average. A measurable tie-breaking rule can assign each observation to one of its nearest centers. Because both losses use the same nearest-center rule, their Voronoi cells agree for a given codebook, including the same possible ties.

The cellwise definitions require the appropriate moments. If \(P(A)>0\), then \(E[\|X\|\mid X\in A]\leq E[\|X\|]/P(A)\); likewise, \(E[\|X\|^2\mid X\in A]\leq E[\|X\|^2]/P(A)\). Thus a finite global first moment ensures finite conditional Euclidean-distance loss in every positive-probability cell, and a finite global second moment ensures finite conditional squared-distance loss there. A weaker, mismatched assumption need not suffice: a finite first moment alone does not guarantee finite squared-distance risk.

The Cellwise Geometric-Median Condition

For a fixed cell, the geometric-median condition can be stated without assuming that the distribution has a density or that it puts no mass at the candidate median. That qualification matters: the norm is not differentiable when \(X=m\).

Proof. Fix a direction \(h\in\mathbb{R}^d\). For \(t>0\), consider the directional difference quotient \((g(m+th)-g(m))/t\). For \(X\ne m\), its integrand converges as \(t\downarrow0\) to \((m-X)\cdot h/\|m-X\|\). For \(X=m\), the integrand equals \(\|h\|\). The absolute value of each difference quotient is at most \(\|h\|\), by the reverse triangle inequality. Dominated convergence therefore gives the directional derivative

The function \(g\) is convex, since it is an expectation of convex functions. A point minimizes a convex function if and only if all its one-sided directional derivatives there are nonnegative: necessity follows from minimality; for sufficiency, convexity makes the slope from \(m\) to \(m+h\) at least the right derivative at zero. Thus \(m\) minimizes \(g\) exactly when \(a\cdot h+p\|h\|\geq0\) for every \(h\). By Cauchy–Schwarz, this holds if \(\|a\|\leq p\). Conversely, if \(\|a\|>p\), taking \(h=-a\) gives \(-\|a\|^2+p\|a\|<0\). This proves the condition. \(\square\)

When \(P(X=m)=0\), the condition reduces to a zero vector expectation of the unit directions from observations toward \(m\). When there is an atom at \(m\), its probability supplies the allowance \(P(X=m)\); simply setting a derivative equal to zero would miss this case.

What Changes for a Whole Codebook?

For a fixed assignment of observations to cells, the squared-loss objective separates into one term per cell, whose unrestricted minimizer for each positive-probability cell is its conditional mean. Under Euclidean distance, the unrestricted minimizer of each such term is a conditional geometric median. With centers constrained to \(C\), each cellwise loss must instead be minimized over \(C\); an unrestricted minimizer is valid when it belongs to \(C\). The condition above characterizes unrestricted geometric medians.

This is a cellwise statement, not a recipe that independently chooses all centers and thereby guarantees a global optimum. Changing a center can change which observations are nearest to which center. At a global optimum, replacing a center by a better representative in \(C\) for its current cell would reduce the loss for that fixed assignment, and the nearest-center loss after replacement can only be smaller than or equal to the loss under that assignment. Thus a positive-probability cell of a global optimum must have a representative minimizing its conditional loss over \(C\). A zero-probability cell imposes no such condition, and its center may be arbitrary. Ties can be handled by the measurable partition convention; the cellwise argument uses the assigned observations in each cell.

Which Consistency Arguments Remain Valid?

The empirical K-means consistency arguments based on compact codebooks, uniform convergence of empirical risks, and set-valued argmin consistency transfer to K-medians when their assumptions are adjusted to the loss. The key issue is not the name of the algorithm but whether the chosen loss has finite expectation and whether the empirical risks converge uniformly over the allowed codebooks.

For example, suppose \(C\) is compact, \(X_1,\ldots,X_n\) are independent and identically distributed, and \(E\|X\|<\infty\). On a bounded set of centers, the Euclidean loss is bounded by \(\|X\|+M\) for a suitable finite \(M\); changing a center by distance \(\delta\) changes its distance loss by at most \(\delta\). These bounds give an integrable envelope and a uniform Lipschitz bound in the codebook. A finite-net argument together with the law of large numbers then gives uniform convergence of the empirical Euclidean-distance risks. For squared loss, the corresponding envelope is bounded by a constant times \(1+\|X\|^2\), so a finite second moment is the natural sufficient moment assumption for that argument.

Proof. Continuity and compactness imply that \(\mathcal{M}\) is nonempty and compact. Fix \(\epsilon>0\). The compact set of codebooks at distance at least \(\epsilon\) from \(\mathcal{M}\) contains no minimizer. If that set is nonempty, continuity and compactness imply that its minimum risk exceeds \(\min R\) by some gap \(\Delta_\epsilon>0\). On the event that \(\sup_{c\in C^K}|R_n(c)-R(c)|<\Delta_\epsilon/3\) and the optimization error is less than \(\Delta_\epsilon/3\), an approximate minimizer cannot lie in that set: its empirical risk would exceed the empirical risk of a population minimizer. Uniform convergence in probability and the \(o_p(1)\) optimization error make the probability of the complementary event tend to zero. If the set is empty, the distance is already less than \(\epsilon\). Thus \(P(\operatorname{dist}(\hat c_n,\mathcal{M})\geq\epsilon)\to0\) for every \(\epsilon>0\). \(\square\)

This result does not require a unique population optimum; it gives convergence to the full minimizing set. Consequently, the set-valued consistency argument remains valid for K-medians under the corresponding uniform-convergence conditions. The uniqueness-based conclusion that a codebook converges to one particular codebook requires uniqueness just as before. Nor do rates transfer automatically: squared loss can yield quadratic growth near an optimum under suitable assumptions, whereas Euclidean loss has different local behavior. Conclusions that convert center error into partition error also need their own boundary and margin conditions. Although the nearest-center partitions for a fixed codebook are the same for both losses, risk and center behavior can differ.

Common Mistakes and Practical Consequences

• Using the mean for every distortion. The mean minimizes squared distance, not generally Euclidean distance. For K-medians, use the cellwise geometric-median condition.
• Differentiating through an atom as if the norm were smooth. At \(X=m\), the directional derivative contributes \(P(X=m)\|h\|\). The resulting condition is an inequality, not necessarily a zero-gradient equation.
• Assuming every cell has a unique representative. Geometric medians can form a set, as the symmetric two-point example shows. An unused cell has no conditional representative requirement at all.
• Using the wrong moment assumption. A finite first moment suffices for Euclidean-distance risk; squared-distance risk generally requires a finite second moment. A finite global moment of the matching order also ensures finite conditional loss in every positive-probability cell.
• Transferring a rate or partition bound without checking its assumptions. Uniform convergence and compactness support consistency, but curvature and boundary conditions used for sharper conclusions must be checked for the loss and distribution at hand.