Finite Quantization, Lloyd Iteration, and Compact Companders

Since $S$ is nonempty and each $w_i>0$, $W_S>0$, so ${\mu }_S$ is defined and ${\sum }_{i\in S}{w}_i(x_i-{\mu }_S)=0$ by its formula.

Write $x_i-c=(x_i-{\mu }_S)+({\mu }_S-c)$ and expand the squared norm using [A1]. Summing over $S$, the cross term is $2⟨{\sum }_{i\in S}{w}_i(x_i-{\mu }_S),{\mu }_S-c⟩=0$ by step 1.1; the remaining terms give the displayed identity.

The last term in step 2.1 is nonnegative and vanishes exactly when $c={\mu }_S$, because $W_S>0$ and a Euclidean squared norm vanishes exactly at the zero vector. Thus ${\mu }_S$ uniquely minimizes the cost. For empty $S$, the sum has no terms and equals zero for every $c$.

By [F2], $G_g$ is continuous and $G_g^{\mathrm{\prime }}=g$ on $(a,b)$, so it is $C^2$ because $g$ is $C^1$; also $G_g(a)=0$ and $G_g(b)=1$ by [F1]. Since $g$ is positive and continuous on compact $[a,b]$, [F7] gives a positive minimum, and in particular $G_g^{\mathrm{\prime }}(x)>0$ at every interior point.

For $x<y$ in $[a,b]$, [F3] applied to $G_g$ gives $G_g(y)-G_g(x)=g(c)(y-x)>0$. Thus $G_g$ is strictly increasing; [F4] and step 1.1 show its image is all of $[0,1]$. Strict increase makes each preimage unique, so an inverse $\varphi :[0,1]\to [a,b]$ exists.

Fix $u_0\in [0,1]$ and set $x_0=\varphi (u_0)$. For $\epsilon >0$ put $x_{-}=\max (a,x_0-\epsilon )$ and $x_{+}=\min (b,x_0+\epsilon )$. At least one of $x_{-}<x_0$ and $x_0<x_{+}$ holds because $a<b$. Whenever $x_{-}<x_0$ or $x_0<x_{+}$, strict increase gives respectively $u_0-G_g(x_{-})>0$ or $G_g(x_{+})-u_0>0$. Choose $\delta >0$ smaller than each of the positive margins that exists. For $u\in [0,1]$ with $\mathrm{\mid }u-u_0\mathrm{\mid }<\delta$, monotonicity gives $x_{-}\le \varphi (u)\le x_{+}$; at a missing margin $x_{-}=x_0=a$ or $x_{+}=x_0=b$, the domain endpoint supplies that inequality. Hence $\mathrm{\mid }\varphi (u)-x_0\mathrm{\mid }<\epsilon$, proving continuity of $\varphi$.

Fix $u\in (0,1)$, let $x=\varphi (u)$, and for nonzero $h$ with $u+h\in [0,1]$ let $x_h=\varphi (u+h)$. Continuity from step 3.1 gives $x_h\to x$, and injectivity gives $x_h\mathrm{\ne }x$. By [F3], for some ${\xi }_h$ between $x$ and $x_h$, $(\varphi (u+h)-\varphi (u))\mathrm{/}h=1\mathrm{/}g({\xi }_h)$. As $h\to 0$, ${\xi }_h\to x$ and $g({\xi }_h)\to g(x)>0$, so ${\varphi }^{\mathrm{\prime }}(u)=1\mathrm{/}g(\varphi (u))$. The same one-sided quotient argument applies at $u=0,1$.

The formula for ${\varphi }^{\mathrm{\prime }}$ is continuous on $[0,1]$ because $g\circ \varphi$ is continuous and positive. Differentiating it on $(0,1)$ using [F5] and [F6] gives ${\varphi }^{\mathrm{\prime }\mathrm{\prime }}(u)=-g^{\mathrm{\prime }}(\varphi (u))\mathrm{/}g(\varphi (u){)}^3$. The right-hand side extends continuously to $[0,1]$ because $g^{\mathrm{\prime }}$ and $\varphi$ are continuous and the denominator stays positive. Applying [F3] to ${\varphi }^{\mathrm{\prime }}$ on intervals with an endpoint at $0$ or $1$ shows its one-sided difference quotient tends to that continuous extension. Together with step 4.1, this proves the stated $C^2$ regularity and formulas.

For fixed $i,j$, the difference $\mathrm{\parallel }x-c_i{\mathrm{\parallel }}_2^2-\mathrm{\parallel }x-c_j{\mathrm{\parallel }}_2^2$ is a continuous polynomial in the coordinates of $x$. Therefore its strict-negative set is open and its nonpositive set is closed; the finite intersections defining each $C_i(c)$ in [F1] are Borel.

The finite list of distances has a minimum at each $x\in X$, and the least minimizing index is unique. The tie inequalities in [F1] therefore make the cells a disjoint partition of $X$; the inverse image of each singleton index is relatively Borel by step 1.1, so the finite-valued index map is Borel.

For each coordinate, $(x_{\mathrm{\ell }}-c_{i,\mathrm{\ell }}{)}^2\le 2x_{\mathrm{\ell }}^2+2c_{i,\mathrm{\ell }}^2$, since $-2x_{\mathrm{\ell }}{c}_{i,\mathrm{\ell }}\le x_{\mathrm{\ell }}^2+c_{i,\mathrm{\ell }}^2$. Summing coordinates and integrating over the partition gives $D_{\mu }(Q_c;c)\le 2\int \mathrm{\parallel }x{\mathrm{\parallel }}_2^{2}d\mu (x)+2{\max }_{1\le i\le k}\mathrm{\parallel }{c}_i{\mathrm{\parallel }}_2^2<\mathrm{\infty }$, so the distortion is well-defined and finite.

The boundary sequence ${\beta }_0<\cdots <{\beta }_N$ is strictly increasing by [F2], with ${\beta }_0=a$ and ${\beta }_N=b$. Thus the intervals in [F1] are pairwise disjoint Borel sets whose union is $[a,b]$.

Each index preimage is one of those Borel intervals, so the finite-valued index map is Borel and defines a quantizer as in [F3]. Each reproduction point lies in $[a,b]$ by [F1] and [F2], so $\mathrm{\mid }x-r_j\mathrm{\mid }\le b-a$ on cell $j$; hence $0\le D_N(f,g)\le (b-a{)}^2{\int }_a^{b}f(x)dx=(b-a{)}^2<\mathrm{\infty }$.

At pass $t$, the assignments in [F1] minimize each point's squared distance for the fixed tuple $c^t$, so their assigned cost is exactly $J(c^t)$ from [F3].

Replacing the centers by cluster centroids changes the assigned cost by subtracting ${\sum }_{j:S_j^t\mathrm{\ne }\mathrm{\varnothing }}{W}_{S_j^t}\mathrm{\parallel }{c}_j^t-{\mu }_{S_j^t}{\mathrm{\parallel }}_2^2$, by [F2]; empty clusters contribute no cost and their centers are unchanged by [F1]. If any center changes, one nonempty-cluster term is positive. Reassigning to nearest centers cannot increase cost, so $J(c^{t+1})<J(c^t)$.

Every center value occurring in the iteration is either its own initial value or the centroid of one of the at most $2^N-1$ nonempty indexed subsets of the data; thus each center has at most $2^N$ possible values and there are at most $2^{Nk}$ possible ordered center tuples.

A changed pass cannot revisit a previous center tuple, because $J$ is a function of that tuple and strictly decreases at every changed pass by step 1.2. Hence at most $2^{Nk}-1$ passes change the tuple; the next pass leaves it unchanged and the algorithm stops, for at most $2^{Nk}$ passes.

At the stopping pass, the tuple is unchanged. The deterministic nearest-center rule therefore gives the same assignments on the next evaluation, and the update formula in [F1] already made every nonempty center its assigned centroid. Thus the returned pair is an assignment/centroid fixed point.

One pass evaluates $Nk$ squared distances in $d$ coordinates and performs at most $O(Nd+kd)$ accumulation/update work, which is $O(Nkd)$ since $N,d,k\ge 1$. Multiplying by the pass bound gives $O(2^{Nk}Nkd)$ exact operations; this exponential bound makes no polynomial-time claim.

The assignment set $\{1,\dots ,k{\}}^N$ has exactly $k^N$ elements, so the finite ordered loop in [F1] terminates and retains an assignment $a^{\ast }$ of minimum centroid-adjusted assigned cost $L_{\ast }$.

Fix any center tuple $c$ and assign each point to its least-index nearest center, obtaining $a(c)$. By [F2], the centroid-adjusted cost of this assignment is at most its cost at $c$, so $L_{\ast }\le L(a(c))\le J(c)$ by [F3].

Let $c^{\ast }$ be the tuple retained for $a^{\ast }$. Reassigning $a^{\ast }$ to nearest centers cannot increase its cost, hence $J(c^{\ast })\le L_{\ast }$. Step 1.2 gives $L_{\ast }\le J(c)$ for every $c$, in particular $L_{\ast }\le J(c^{\ast })$; therefore $J(c^{\ast })=L_{\ast }$ and $J(c^{\ast })\le J(c)$ for every $k$-center tuple. The returned tuple is globally minimizing.

Each of the $k^N$ assignments can be grouped, centered and costed in $O((N+k)d)$ exact operations; the final nearest reassignment costs $O(Nkd)$, which is bounded by $O(k^N(N+k)d)$ for $N,k\ge 1$. This proves the stated operation count without a bit-complexity claim.

Put $v_j=(j-\frac{1}{2})\mathrm{/}N$, $I_j=[(j-1)\mathrm{/}N,j\mathrm{/}N]$, and $F(u)=f(\varphi (u))\mathrm{/}g(\varphi (u))$. For $h_j(x)=f(x)(x-\varphi (v_j){)}^2$, its primitive $A_j(x)={\int }_a^x{h}_j(s)ds$ satisfies $A_j^{\mathrm{\prime }}=h_j$ by [F4]. The chain rule [F5] applied to $A_j\circ \varphi$ on $I_j$, followed by endpoint evaluation using [F4], gives $D_N(f,g)={\sum }_{j=1}^N{\int }_{I_j}F(u)(\varphi (u)-\varphi (v_j){)}^{2}du$, because [F2] gives ${\varphi }^{\mathrm{\prime }}=1\mathrm{/}(g\circ \varphi )$ and [F1] gives the reproduction point $\varphi (v_j)$. The distortion is well-defined by [F3].

By the chain rule [F5] and quotient rule [F6], $F$ is $C^1$; the functions ${\varphi }^{\mathrm{\prime }}$, ${\varphi }^{\mathrm{\prime }\mathrm{\prime }}$, $F$ and $F^{\mathrm{\prime }}$ are continuous on compact $[0,1]$, so [F8] gives finite bounds $M_1=\mathrm{\parallel }{\varphi }^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}$, $M_2=\mathrm{\parallel }{\varphi }^{\mathrm{\prime }\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}$, $M_F=\mathrm{\parallel }F{\mathrm{\parallel }}_{\mathrm{\infty }}$, and $M_{F^{\mathrm{\prime }}}=\mathrm{\parallel }{F}^{\mathrm{\prime }}{\mathrm{\parallel }}_{\mathrm{\infty }}$, independent of $N,j$. If $\delta =u-v_j$ and $e=\varphi (u)-\varphi (v_j)-{\varphi }^{\mathrm{\prime }}(v_j)\delta$, [F7] applied to ${\varphi }^{\mathrm{\prime }}$ and $F$, together with [F4], gives $\mathrm{\mid }e\mathrm{\mid }\le M_2\mathrm{\mid }\delta {\mathrm{\mid }}^2\mathrm{/}2$ and $\mathrm{\mid }F(u)-F(v_j)\mathrm{\mid }\le M_{F^{\mathrm{\prime }}}\mathrm{\mid }\delta \mathrm{\mid }$. Expanding the square therefore bounds the absolute difference under consideration by $M_{F^{\mathrm{\prime }}}{M}_1^2\mathrm{\mid }\delta {\mathrm{\mid }}^3+M_F(M_1{M}_2\mathrm{\mid }\delta {\mathrm{\mid }}^3+M_2^2\mathrm{\mid }\delta {\mathrm{\mid }}^4\mathrm{/}4)$. Since $\mathrm{\mid }\delta \mathrm{\mid }\le 1\mathrm{/}(2N)\le 1\mathrm{/}2$, this is at most $C\mathrm{\mid }\delta {\mathrm{\mid }}^3$ for $C=M_{F^{\mathrm{\prime }}}{M}_1^2+M_F{M}_1{M}_2+M_F{M}_2^2\mathrm{/}8$, which is independent of $N,j$.

On $I_j$, direct integration gives ${\int }_{I_j}{\delta }^{2}du=1\mathrm{/}(12N^3)$ and ${\int }_{I_j}\mathrm{\mid }\delta {\mathrm{\mid }}^{3}du=1\mathrm{/}(32N^4)$. Thus step 1.2 gives $D_N(f,g)=\frac{1}{12N^3}{\sum }_{j=1}^{N}H(v_j)+E_N$ with $\mathrm{\mid }{E}_N\mathrm{\mid }\le C\mathrm{/}(32N^3)$, where $H(u):=F(u){\varphi }^{\mathrm{\prime }}(u{)}^2=f(\varphi (u))\mathrm{/}g(\varphi (u){)}^3$.

Multiplying by $N^2$ gives $N^2{D}_N(f,g)=\frac{1}{12N}{\sum }_{j=1}^{N}H(v_j)+N^2{E}_N$, with $\mathrm{\mid }{N}^2{E}_N\mathrm{\mid }\le C\mathrm{/}(32N)\to 0$. By [F9], $H$ is uniformly continuous on $[0,1]$. Given $\epsilon >0$, choose $\delta >0$ such that $\mathrm{\mid }H(u)-H(v)\mathrm{\mid }<\epsilon$ whenever $\mathrm{\mid }u-v\mathrm{\mid }<\delta$. Let $P(u):={\int }_0^{u}H(s)ds$; [F4] gives $P^{\mathrm{\prime }}=H$ and $P(1)-P(0)={\int }_0^{1}H$. For $N$ with $1\mathrm{/}(2N)<\delta$, the mean value theorem [F7] on each $I_j$ gives ${\xi }_j\in ((j-1)\mathrm{/}N,j\mathrm{/}N)$ with $P(j\mathrm{/}N)-P((j-1)\mathrm{/}N)=H({\xi }_j)\mathrm{/}N$. Since $\mathrm{\mid }{\xi }_j-v_j\mathrm{\mid }<1\mathrm{/}(2N)<\delta$, telescoping gives $\mid \frac{1}{N}{\sum }_{j=1}^{N}H(v_j)-{\int }_0^{1}H(u)du\mid \le \frac{1}{N}{\sum }_{j=1}^N\mathrm{\mid }H(v_j)-H({\xi }_j)\mathrm{\mid }<\epsilon$. Thus the midpoint sums converge to ${\int }_0^{1}H(u)du$.

Let $P(x)={\int }_a^{x}f(s)\mathrm{/}g(s{)}^{2}ds$. The integrand is continuous because $g$ is positive on the compact interval, so [F4] gives $P^{\mathrm{\prime }}=f\mathrm{/}{g}^2$. By [F5] and [F2], $(P\circ \varphi {)}^{\mathrm{\prime }}(u)=f(\varphi (u))\mathrm{/}g(\varphi (u){)}^3=H(u)$. Evaluating this primitive at $0,1$ by [F4], using $\varphi (0)=a$ and $\varphi (1)=b$, gives ${\int }_0^{1}H(u)du={\int }_a^{b}f(x)\mathrm{/}g(x{)}^{2}dx$.

Steps 3.1 and 3.2 identify the limit of $N^2{D}_N(f,g)$ with the displayed integral, proving the theorem.