Theoretical Allocation of Shape and Gain Rates

Here we consider the theoretical tradeoff between allocating transmission rate to the gain quantizer and the shape quantizer. In order to facilitate analysis we use high resolution assumptions. For general shape-gain quantizers this is an unsolved problem. However, if: (i) the source is Gaussian; (ii) the shape codebook is based on a lattice; and (iii) the gain quantizer is independent of the shape quantizer, then it is possible to obtain a high resolution analytic solution. This may help to provide intuition about the more general case too.

Since the transmission rate $R$, the shape quantizer rate $R_s$, and the gain quantizer rate $R_g$ are related by $R = R_s + R_g$ we can write the shape distortion and the high resolution gain distortion as

$$D_s \sim (k-1)\sigma^2 G(\Lambda) V(\Lambda)^{2 \over k-1} \sim C_s2^{-2R_s \left( \frac{k}{k-1} \right) }$$ (22)

$$D_g \sim C_g2^{-2R_g k} = C_g2^{-2k(R-R_s)}$$ (23)

where (22) follows using (19) and where (23) holds for large $R_g$ from Bennett's integral [4], with $C_s$ and $C_g$ constants that are independent of $R_s$ and $R_g$. To determine the growth rate of $R_s$ as a function of $R$ that minimizes $D= D_s + D_g$ one can intuitively reason that the asymptotic expressions for $D_s$ and $D_g$ must decay at the same rate. Equating the exponents $2R_s \left( \frac{k}{k-1} \right) = 2k(R-R_s)$ gives $R_s = \left(\frac{k-1}{k}\right)R$, which gives an accurate first-order approximation of $R_s$. Indeed, this follows the intuition that the shape codebook based on a $(k-1)$-dimensional lattice and the gain codebook based on a scalar quantity should have a rate allocation of approximately $R(k-1)/k$ and $R/k$, respectively, for the rate $R$, $k$-dimensional vector quantizer. The exact optimal choice of $R_s$ is given in the following theorem, where it is shown that $D \sim A 2^{-2R}$, with the constant $A$ identified and depending only on the vector dimension $k$, the source variance $\sigma^2$, and the the normalized second moment $G(\Lambda)$ of the lattice $\Lambda$.

Theorem 1   Let $k>1$, let $X\in{\mathbb{R}}^k$ be an uncorrelated Gaussian vector with zero mean and component variances $\sigma^2 < \infty$, and let $\Lambda$ be a lattice in ${\mathbb{R}}^{k-1}$ with normalized second moment $G(\Lambda)$. Suppose $X$ is quantized by a $k$-dimensional shape-gain vector quantizer at rate $R = R_s + R_g$ (where $R_s$ and $R_g$ are the shape and gain quantizer rates) with independent shape and gain encoders and whose shape codebook is a wrapped spherical code constructed from $\Lambda$. Then the asymptotic decay of the minimum mean squared quantization error $D$ is given by

$$\lim_{R\to\infty} D 2^{2R} = \frac{k}{(k-1)^{1-\frac{1}{k}}} \cdot C_g^{\frac{1}{k}} C_s^{1-\frac{1}{k}}$$ (24)

and is achieved by $R_s = R^*_s$ and $R_g = R^*_g$, where

$$R^*_s = \left(\frac{k-1}{k}\right) \left[ R + \frac{1}{2k} \log_2 \left( \frac{C_s}{C_g}\cdot\frac{1}{k-1}\right) \right]$$ (25)

$$R^*_g = \left(\frac{1}{k}\right) \left[ R - \frac{k-1}{2k} \log_2 \left( \frac{C_s}{C_g}\cdot\frac{1}{k-1}\right) \right]$$ (26)

$$C_s = \sigma^2 \cdot (k-1) G(\Lambda) \left( \frac{2\pi^{k/2}}{\Gamma (k/2)}\right)^{\frac{2}{k-1}}$$

$$C_g = \sigma^2 \cdot \frac{3^{k/2}\Gamma^3\left(\frac{k+2}{6}\right)} {8k\Gamma (k/2)} .$$

Proof. Let $D_s$ and $D_g$ be the distortions of the shape and gain quantizers at rates $R_s$ and $R_g$, respectively. From (11) we have

$$D = \inf_{\substack{R_s, R_g \\ R_s + R_g = R}} (D_s + D_g) ,$$ (27)

and therefore

$$D 2^{2R} = s_R 2^{-2a_R \left(\frac{k}{k-1}\right)} + g_R 2^{2ka_R}$$ (28)

where

$$a_R = R^*_s- \left(\frac{k-1}{k}\right)R$$

$$s_R = D_s 2^{2R^*_s\left(\frac{k}{k-1}\right)}$$

$$g_R = D_g 2^{2k(R-R^*_s)}.$$

Also, $R^*_s\to\infty$ and $R-R^*_s= R^*_g\to\infty$ as $R \to\infty$, for otherwise either $D_s$ or $D_g$ (and hence $D$) would be bounded away from zero (i.e. not achieving the minimum MSE quantization). Define the quantity

$$C_g = \lim_{R\rightarrow\infty} g_R$$

$$= \frac{\Vert f_g\Vert _{1/3}}{12k}$$ (29)

$$= \frac{1}{12k} \left(\int_0^\infty \vert f_g(r)\vert^{1/3}dr\right)^3$$

$$= \frac{1}{\Gamma(k/2) (2\sigma^2)^{k/2} 6k}$$

$$\cdot\left( \int_0^\infty r^{(k-1)/3} e^{-r^2/(6\sigma^2)} dr \right)^3$$ (30)

$$= \frac{1}{\Gamma(k/2) (2\sigma^2)^{k/2} 6k}$$

$$\cdot\left( 2^{(k-4)/6} (3\sigma^2)^{(k+2)/6} \int_0^\infty t^{(k-4)/6}e^{-t} dt\right)^3$$ (31)

$$= \sigma^2 \cdot \frac{3^{\frac{k}{2}}\Gamma^3\left(\frac{k+2}{6}\right) } {8k\Gamma (k/2)}$$ (32)

where (29) follows from Bennett's integral [4]; (30) follows using the density function $f_g$ of the gain $g = \Vert X\Vert$ from (1); (31) follows by substituting $r^2=6\sigma^2 t$; and (32) follows from [39, pg. 342, eq. 662].

Define the quantity

$$C_s = \lim_{R\rightarrow\infty} s_R$$ (33)

$$= \lim_{R\rightarrow\infty} \left( {1 \over k} (E[g^2] - E[(g-\hat{g})^2])E[\Vert S-\hat{S}\Vert^2] \right.$$

$$\hspace*{1cm}\left. \cdot 2^{2R^*_s\left(\frac{k}{k-1}\right)} \right)$$ (34)

$$= \sigma^2 \lim_{R\rightarrow\infty} E[\Vert S-\hat{S}\Vert^2] \cdot 2^{2R^*_s\left(\frac{k}{k-1}\right)}$$ (35)

$$= \sigma^2 (k-1)G(\Lambda) \lim_{R\rightarrow\infty} V(\Lambda)^\frac{2}{k-1}\cdot 2^{2R^*_s\left(\frac{k}{k-1}\right)}$$ (36)

$$= \sigma^2 (k-1)G(\Lambda) S_k^\frac{2}{k-1}$$ (37)

$$= \sigma^2 (k-1)G(\Lambda) \left(2 \pi^{k/2} / \Gamma(k/2)\right)^\frac{2}{k-1}$$ (38)

where (34) follows from (13); (35) follows from (3) and $\lim_{R\rightarrow\infty} E[(g-\hat{g})^2]=0$; (36) follows from (20); (37) follows from (21); and (38) follows from $S_k = 2 \pi^{k/2} / \Gamma(k/2)$. Note that the limit in (33) exists by working backwards from (37).

Let $a = \left(\frac{k-1}{2k^2}\right) \log_2 \left( \frac{C_s}{C_g}\cdot\frac{1}{k-1}\right)$ and notice that the unique minimum value of the function $f(x) = C_s2^{-2x \left(\frac{k}{k-1}\right)} + C_g2^{2kx}$ is achieved at $x=a$, since $f$ is strictly convex and $f'(a)=0$.

Suppose $D_s$ and $D_g$ are the distortions corresponding to $R_s = \left(\frac{k-1}{k}\right)R$. Then

$$D 2^{2R} \leq (D_s + D_g) 2^{2R}$$

$$= D_s 2^{2\left(\frac{k}{k-1}\right)R_s} + D_g 2^{2k(R-R_s)}$$

$$\longrightarrow C_s + C_g$$

as $R \rightarrow\infty$. Thus $D2^{2R}$ is bounded as $R \to\infty$. In addition, $s_R$ and $g_R$ are bounded away from zero for sufficiently large $R$. Thus, $a_R$ is bounded, from (28), and hence for $k\ge 2$,

$${\left\vert D 2^{2R} - C_s2^{-2a_R \left(\frac{k}{k-1}\right)} - C_g2^{2ka_R}\right\vert}$$

$$\le \vert s_R - C_s\vert \cdot 2^{-2a_R \left(\frac{k}{k-1}\right)} + \vert g_R - C_g\vert \cdot 2^{2ka_R}$$

$$\longrightarrow 0 \ R\to\infty .$$

Since

$$C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka} \le C_s2^{-2a_R \left(\frac{k}{k-1}\right)} + C_g2^{2ka_R}$$

for all $R$, we have

$$D 2^{2R} \ge D 2^{2R} - \left( C_s2^{-2a_R \left(\frac{k}{k-1}\right)} + C_g2^{2ka_R} \right)$$

$$+ \left( C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka}\right) .$$

So for any $\epsilon>0$, we have $D 2^{2R} \ge C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka} - \epsilon$ for sufficently large $R$. Thus

$$\liminf_{R\to\infty} D 2^{2R} \ge C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka} .$$ (39)

On the other hand, suppose $D_s$ and $D_g$ are the distortions corresponding to $R_s = \left( \frac{k-1}{k}\right)R + a$. Then from (27),

$$D 2^{2R} \le 2^{2R} (D_s + D_g)$$ (40)

$$= D_s 2^{2R_s \left(\frac{k}{k-1}\right)} 2^{-2a \left(\frac{k}{k-1}\right)}$$

$$+ D_g 2^{2k(R-R_s)} 2^{2ak}$$ (41)

$$\longrightarrow C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka}$$ (42)

as $R \rightarrow\infty$. Thus,

$$\limsup_{R\to\infty} D 2^{2R} \le C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka} .$$ (43)

Combining (39) and (43) gives

$$\lim_{R\to\infty} D 2^{2R} = C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka}$$

which is achieved by $R^*_s= \left( \frac{k-1}{k}\right)R + a$. Substituting the definition of $a$ into $C_s2^{-2a \left(\frac{k}{k-1}\right)} + C_g2^{2ka}$, $R^*_s= \left( \frac{k-1}{k}\right)R + a$, and $R^*_g= R - R^*_s$, gives (24), (25), and (26), respectively. $\qedsymbol$

Note that for large $R$, the optimal allocation of transmission rate between the shape quantizer and the gain quantizer is from (26) approximately $R^*_s\approx \left(1 - \frac{1}{k}\right) R$ and $R^*_g\approx \frac{1}{k} R$. This means that the shape codebook should have about $2^{(k-1)R}$ codevectors and the gain codebook should have about $2^R$ scalar codepoints, as intuition would indicate. This corresponds roughly to what was observed in the experimental rate allocation optimization. In simulations, we observed that the optimal gain codebook rate was within 8% of this figure when $R\ge 3$ and within 1% when $R\ge 5$.