Label Switching and Identifiability of Optimal Codebooks

Why Labels and Identifiability Must Be Separated

A codebook is often written as an ordered list of centers, even though the order has no effect on which observations are represented or on the resulting distortion. This creates a basic distinction: two lists may differ only because their center labels have been switched, or they may describe genuinely different geometric arrangements. The first is a representational ambiguity; the second is nonuniqueness of the optimal solution itself.

To make that distinction precise, compare codebooks after the best possible relabeling. This gives a natural distance for discussing convergence and uniqueness without treating arbitrary center labels as meaningful. Separately, symmetries of the data distribution can map one optimal arrangement to another while leaving its distortion unchanged.

Codebook Distance Modulo Permutations

Let \(X\) be a random vector in \(\mathbb{R}^d\) with \(E\|X\|^2<\infty\), and let a codebook contain \(K\) centers. For an ordered codebook \(c=(c_1,\ldots,c_K)\), its squared-distance quantization risk is

R(c)=E\left[\min_{1\leq j\leq K}\|X-c_j\|^2\right].

The risk depends on the centers, not their labels: any permutation of the entries gives the same nearest-center distances. Write \(S_K\) for the set of permutations of \(\{1,\ldots,K\}\). For two ordered codebooks \(c\) and \(c'\), define

d_{\mathrm{perm}}(c,c') = \min_{\sigma\in S_K} \left(\sum_{j=1}^K\|c_j-c'_{\sigma(j)}\|^2\right)^{1/2}.

This is the ordinary Euclidean distance between the two lists after choosing the best matching of their centers. The minimization over permutations is essential: it prevents a mere change of labels from appearing as a change in the represented codebook.

Definition: Two ordered codebooks are equivalent up to permutation if one is obtained from the other by reordering its centers. Their distance modulo permutations is \(d_{\mathrm{perm}}\). Unordered codebooks can be viewed as equivalence classes of ordered codebooks, with \(d_{\mathrm{perm}}\) as the distance between classes.

This definition remains valid when some centers coincide. In that case, more than one permutation may give the same matching, but the minimum distance is still well defined. The distance is nonnegative and symmetric, and it is zero exactly when the two lists are permutations of one another. It also satisfies the triangle inequality. Indeed, choose permutations that attain the minimum matching from \(c\) to \(c'\) and from \(c'\) to \(c''\). Composing those permutations gives a matching from \(c\) to \(c''\); the Euclidean triangle inequality in the product space \((\mathbb{R}^d)^K\) bounds its distance by \(d_{\mathrm{perm}}(c,c')+d_{\mathrm{perm}}(c',c'')\). Since \(d_{\mathrm{perm}}(c,c'')\) is the minimum over matchings, it is no larger than this bound.

Worked Example: A Label Switch Has Zero Quotient Distance

Suppose \(X\) takes the values \(0\) and \(2\), each with probability \(1/2\), and consider \(K=2\). Compare \(c=(0,2)\) with \(c'=(2,0)\). The identity matching gives squared distance

$$ |0-2|^2+|2-0|^2=4+4=8, $$

so the distance under that matching is \(\sqrt{8}\). The permutation that swaps the labels instead gives

$$ |0-0|^2+|2-2|^2=0. $$

Therefore \(d_{\mathrm{perm}}(c,c')=0\). Both codebooks represent exactly the same two centers. Each has risk \(0\), since every possible value of \(X\) is itself a center. The ordered lists differ, but there is no difference between the unordered codebooks.

Minimizers and Genuine Nonuniqueness

Let \(\mathcal{A}\subseteq\mathbb{R}^d\) be an admissible center space, and restrict attention to \(\mathcal{A}^K\). Define the set of ordered population minimizers by

\mathcal{M} = \left\{c\in\mathcal{A}^K: R(c)=\inf_{u\in\mathcal{A}^K}R(u)\right\}.

A population minimizer is unique modulo permutations if every two elements of \(\mathcal{M}\) have distance zero under \(d_{\mathrm{perm}}\). Equivalently, all ordered minimizers are reorderings of one fixed codebook. This is the relevant form of uniqueness when center labels are not part of the scientific target.

Theorem: Suppose the admissible set \(\mathcal{A}^K\) is invariant under permutations. For every \(c\in\mathcal{A}^K\) and every \(\sigma\in S_K\), \(R(c_{\sigma(1)},\ldots,c_{\sigma(K)})=R(c)\). Consequently, if \(c\) is a minimizer, all of its label permutations are minimizers.

Proof. For each fixed value \(x\),

\min_{1\leq j\leq K}\|x-c_{\sigma(j)}\|^2 = \min_{1\leq j\leq K}\|x-c_j\|^2,

because \(\sigma\) merely reorders the same \(K\) terms. Taking expectations gives equality of the risks. A permutation of a minimizer is admissible by the assumed invariance of the feasible set, so it attains the same minimum risk and is also a minimizer. \(\square\)

The theorem explains why ordered minimizers should not be treated as identifiable objects unless labels have been given an external meaning. It does not, however, establish uniqueness modulo permutations: there may be several different unordered minimizing arrangements.

How Distributional Symmetries Create Distinct Optima

A Euclidean isometry has the form \(T(x)=Qx+b\), where \(Q\) is an orthogonal matrix and \(b\in\mathbb{R}^d\). It preserves all pairwise distances. Suppose \(T(X)\) has the same distribution as \(X\), and suppose applying \(T\) to every center preserves the admissible set. Write \(Tc=(T(c_1),\ldots,T(c_K))\).

Theorem: Under these conditions, \(R(Tc)=R(c)\) for every admissible codebook \(c\). In particular, if \(c\) is a population minimizer, then \(Tc\) is also a population minimizer. If \(d_{\mathrm{perm}}(c,Tc)>0\), these are distinct optimal unordered codebooks with the same minimum distortion.

Proof. Since \(T(X)\) and \(X\) have the same distribution, the expectation defining \(R(Tc)\) can be evaluated with \(T(X)\) in place of \(X\). For each \(x\) and each center \(c_j\), the isometry property gives

\|T(x)-T(c_j)\|^2=\|x-c_j\|^2.

It follows that

R(Tc) =E\left[\min_j\|T(X)-T(c_j)\|^2\right] =E\left[\min_j\|X-c_j\|^2\right] =R(c).

The transformed codebook is admissible by assumption. Thus, if \(c\) attains the infimum risk, so does \(Tc\). A positive \(d_{\mathrm{perm}}(c,Tc)\) means no reordering makes the two lists coincide, so the two optimal solutions are geometrically distinct even after labels are ignored. \(\square\)

The invariance assumption on the distribution matters. A symmetric-looking center arrangement alone does not imply equal risk: it is the distribution, together with the admissible set, that must be preserved by the transformation.

Worked Example: Three Distinct Optima for an Equilateral Distribution

Let \(X\) be equally likely to be one of the three vertices of an equilateral triangle of side length \(a>0\), and take \(K=2\) with unrestricted centers in \(\mathbb{R}^2\). Any assignment of the three vertices to two nonempty clusters puts one vertex alone and two vertices together. For a pair at distance \(a\), the squared-distance cost is minimized at the midpoint, where each vertex is \(a/2\) from the center. Since each vertex has probability \(1/3\), the pair contributes

\frac{1}{3}\left(\frac a2\right)^2 + \frac{1}{3}\left(\frac a2\right)^2 = \frac{a^2}{6}.

The singleton contributes zero when its center is placed at that vertex. This lower bound is attained: put one center at the singleton and the other at the midpoint of the paired vertices. Each paired vertex is closer to the midpoint than to the singleton, and the singleton is closest to its own center. Thus the nearest-center risk is \(a^2/6\).

To see that no smaller risk is possible, assign each vertex to a nearest center for any proposed codebook. If both clusters are nonempty, the sum of squared distances within each cluster is at least its value at the cluster mean; the pair therefore costs at least \(a^2/6\), and the singleton costs at least zero. If all vertices are assigned to one center, the minimum possible risk is the variance around their mean, which is \(a^2/3\), larger than \(a^2/6\). Thus the minimum distortion is \(a^2/6\).

There are three ways to choose which vertex is alone, producing three different unordered codebooks. Rotating the triangle by \(120\) degrees preserves the distribution and cycles these three solutions. They are not label permutations of one another: each has a different triangle vertex as its singleton center. This is genuine nonuniqueness, not label switching.

Uniqueness Can Hold After Labels Are Removed

Symmetry can generate multiple optima, but it does not follow that every distribution has such ambiguity. A distribution without a relevant symmetry may have just one optimal unordered codebook. The next example checks this directly using cluster costs.

Worked Example: A Unique Unordered Optimum on Three Points

Let \(X\) be equally likely to be \(0\), \(1\), or \(4\) on the real line, with \(K=2\). If two points \(u\) and \(v\) are assigned to one center, their minimum weighted squared-distance cost is achieved at their midpoint and equals

\frac{1}{3}\left(\frac{u-v}{2}\right)^2 + \frac{1}{3}\left(\frac{u-v}{2}\right)^2 = \frac{(u-v)^2}{6}.

The possible pairs have costs \(1/6\) for \(\{0,1\}\), \(3/2\) for \(\{1,4\}\), and \(8/3\) for \(\{0,4\}\). The smallest is \(1/6\), obtained by pairing \(0\) and \(1\). The centers \(1/2\) and \(4\) realize that cost and give the stated assignments: \(0\) and \(1\) are each \(1/2\) from \(1/2\), while \(4\) is at its own center.

If all three points are assigned to one center, the minimizing center is their mean \(5/3\), and the risk is

\frac{1}{3}\left[\left(0-\frac53\right)^2+ \left(1-\frac53\right)^2+ \left(4-\frac53\right)^2\right] = \frac{1}{3}\cdot\frac{78}{9} = \frac{26}{9}.

This is greater than \(1/6\). Every two-center assignment either has two nonempty clusters, in which case one of the three pair costs is a lower bound, or has just one nonempty cluster, in which case the all-point cost is a lower bound. Since the best pair is unique and each cluster cost is minimized at its mean, the only optimal unordered codebook is \(\{1/2,4\}\). Its two possible orderings are label switches, not distinct optima.

What Identifiability Means Here

For codebooks, identifiability depends on the object being targeted. If the centers carry external labels, an ordered representation may be appropriate, and label permutations may matter by convention. In ordinary nearest-center clustering, however, those labels do not alter the partition rule or the distortion. The natural target is therefore an unordered codebook, and uniqueness should be assessed using \(d_{\mathrm{perm}}\).

This distinction is also useful when interpreting convergence. A sequence of ordered estimates can appear not to settle if an algorithm swaps labels between iterations, even while the corresponding unordered codebooks approach the same limit. Conversely, relabeling cannot explain a positive distance between optimal codebooks after the best matching has been applied. Distributional symmetries can yield genuinely distinct minimizers, so one should not claim a unique geometric target merely because a particular optimization run returned one solution.

Common Pitfall

Wrong reasoning: “The ordered minimizer is not unique, so the clustering solution is nonidentifiable.” This may only reflect a permutation of the same centers.
Correction: Compare the codebooks using \(d_{\mathrm{perm}}\). Distance zero means the difference is only labeling; positive distance means the unordered center configurations differ.
Another overreach: “A symmetric distribution guarantees multiple optima.” Symmetry guarantees that a transformed optimum is also optimal when the transformation preserves the admissible set. It yields a distinct unordered optimum only when that transformed codebook is not a permutation of the original.

Key takeaway: Center labels are arbitrary in ordinary quantization, so compare codebooks modulo permutations. Distribution-preserving isometries preserve risk; if they move an optimal codebook to a non-equivalent configuration, the minimum distortion is attained by multiple distinct unordered codebooks.

Check Your Understanding

For each question, distinguish carefully between ordered labels and the underlying unordered codebook.

What does \(d_{\mathrm{perm}}(c,c')=0\) say about two ordered codebooks?
Why does permuting the entries of a codebook leave its quantization risk unchanged?
State the conditions under which an isometry maps an optimal codebook to another optimal codebook.
In the equilateral-triangle example, why are the three optima genuinely distinct rather than label switches?
Can a symmetric distribution have an optimal codebook that is fixed by every symmetry? Explain why distributional symmetry alone does not guarantee a distinct transformed optimum.