Bit Allocation Problem

Say we have a block of RVs $X_{1},\dots,X_{k}$ and they’re scalar quantized. (Note that the $X_{i}$ may have different distributions). The main goal we have here is that we want to minimize the overall MSE $$E\left[ \sum^{k}_{i=1}(X_{i}-Q_{i}(X_{i}))^{2} \right]$$where $Q_{i}$ has $N_{i}$ levels, under the condition that overall no more than $B$ bits are used: $$\sum_{i=1}^{k}\log N_{i}\le B$$where $N_{i}=2^{b_{i}}$ and $\log N_{i}=b_{i}$. Another way to interpret this is that for each RV in our random vector we assign it a $N_{i}$-level quantizer such that we meet our constraint and we wish to optimize it (i.e. minimize collective distortion, $\min \sum_{i=1}^{k}D(Q_{i})$) under this constraint (i.e. keeping collective rate under a specified limit, $B$).

We define $W_{i}$ as the MSE of our constrained and optimal $b_{i}$-bit quantizer: $$W_{i}(b_{i})=\min_{Q:r(Q)\le b_{i}}E[(X_{i}-Q(X_{i}))^{2}]$$We see if $b_{i}$ bits are used to quantize $X_{i}$ optimally then the overall optimal distortion is $$D(\mathbf{b})=\sum_{i=1}^{k}W_{i}(b_{i})$$where $\mathbf{b}=(b_{1},\dots,b_{k})^{T}$.

Simplifications…

Before we state the theorem we must state some high-resolution approximations that are made.

1. High-Resolution Conditions: Each $X_{i}$ has pdf $f_{i}$ and $$W_{i}(b)=\frac{1}{12}\lVert f_{i} \rVert_{\frac{1}{3}}2^{-2b}, \ \ i=1,\dots,k$$

2. Let $\sigma_{i}^{2}=\text{Var}(X_{i})$ and $\tilde{X}_{i}=\frac{X_{i}}{\sigma_{i}}$. Then $\tilde{X}_{i}$ has unit variance (i.e. $\text{Var}(\tilde{X}_{i})=1$) and its pdf $\tilde{f}_{i}(x)=\sigma_{i}f_{i}(\sigma_{i}x)$ satisfies $$\lVert f_{i} \rVert _{\frac{1}{3}}=\lVert \tilde{f}_{i} \rVert _{\frac{1}{3}}\sigma_{i}^{2}$$

3. Hence $$\begin{align*} W_{i}(b)&=\underbrace{ \frac{1}{12}\lVert \tilde{f}_{i} \rVert _{\frac{1}{3}} }_{ h_{i} }\sigma_{i}^{2}2^{-2b}\\ &=h_{i}\sigma_{i}^{2}2^{-2b} \end{align*}$$

   Note

   $h_{i}$ is invariant to scaling and hence, is the same for all $X_{i}$ so we treat it as a constant.