Bit Allocation Analysis

In this section a theory of quantizer-based allocation will be developed in which the relations of bit consumption and quantizer-based allocations are treated formally and then an analysis using these relations is pursued.

The first element of the bit allocation analysis is the set of allocation processes which represents the attainable relations between quantizer-based allocations and bit consumption (where superscript ``T'' means transpose):

Definition 1: Set of Allocation Processes. Given ``m'' competing quantizers $Q_1, \cdots, Q_m$, let $Y$ be the set of attainable combinations of allocation-consumption processes where a process $y \in Y$ is an ordered (m+1)-tuple which describes a relation of bit allocations among competing quantizers and consumption of bits at a given time:

$$y = (y_1 , y_2, \cdots, y_m; y_{m+1})^T$$ (2)

where $y_j \geq 0$ denotes the bit allocation for quantizer $Q_j$, with $j=1, \cdots, m$; the bit consumption is represented by a nonpositive value $y_{m+1} \leq 0$.

The second element of the bit allocation analysis is axiomatic and thus imposes four postulates over the collection $Y$ of consumption-allocation combinations that are attainable at a given time. These axioms indicate the technological possibilities in the allocation problem and take resource limitations into account.

Axiom 1. There exists a finite set $A \equiv [a^1, a^2, \cdots, a^m]$ of basic allocation processes, represented by vectors $a^j = ( a^j_1, a^j_2, \cdots, a^j_{m+1})^T$, $j=1, \cdots, m$, such that the set of allocation process $Y$ can be represented by

$$Y \equiv \{ y \ : \ y = A \cdot \lambda, \ \lambda \stackrel... ...\lambda_j \cdot a^j_i \vert \leq R_i, \ i= 1, \cdots, m+1$} \}$$ (3)

where for $y= A \cdot \lambda$ the basic processes $a^1, a^2, \cdots, a^m$ are operated at intensity $\lambda = (\lambda_1 , \lambda_2, \cdots, \lambda_m)^T$; for some $R_i \geq 0$, $i= 1, \cdots, m+1$, denoting the limitation of use of the resource up to its availability limit.

This means that an allocation process in $Y$ can be expressed as a nonnegative linear combination of ``m'' basic processes $a^1, a^2, \cdots, a^m$, with ``m'' being the number of quantizers $Q_1, \cdots, Q_m$:

$$y = A \cdot \lambda = [a^1, a^2, \cdots, a^m] \cdot \left( \b... ...lambda_m \end{array} \right) = \sum_{j} \lambda_j \cdot a^j$$

such that $\left\vert \sum_{j} \lambda_j \cdot a^j_i \right\vert \leq R_i,$ $i= 1, \cdots, m+1$.

Axiom 2. There exists at least one positive element $y_j$ for some attainable combination $y$ of allocation-consumption processes in the set of allocation processes $Y$.

In other case we have that there is no possibility of bit allocation for some quantizer over $y$ in the set of allocation processes.

Axiom 3. Every positive allocation in any attainable combination $y$ of allocation-consumption processes produces bit consumption.

It means that, $y \geq 0$ (with bit consumption represented by a nonpositive element $y_{m+1}$ of $y$) implies $y \not\in Y$. Given two vectors $u$ and $v$, the notation $u \geq v$ means that $u_i \geq v_i$ for all $i$, and $u_i > v_i$ for at least one $i$. This should be distinguished from the notation $u \stackrel{>}{=} v$ which requires only the first of the above conditions, that is, $u_i \geq v_i$ for all $i$.

Axiom 4. Every combination of quantizer-based allocations and the consequent bit consumption at any given time is irreversible.

That is, $y \in Y$ and $y \not= 0$ imply $-y \not\in Y$.

The following definition introduces the most important concept in bit allocation analysis: Efficient allocation process. A combination $y$ of quantizer-based allocations and bit consumption is called efficient whenever an increase in one quantizer allocation $y_j$ for some $Q_j$ can be achieved only at the cost of a decrease in some other quantizer allocation or increasing bit consumption.

Definition 2: Efficient Allocation Process. Let $Y$ be a set of allocation processes. A process $\hat{y}$ in $Y$ is called efficient allocation process of $Y$ if there does not exists a $y \in Y$ such that $y \geq \hat{y}$.

The notion expressed by this definition is one of efficiency in converting available bit resources into desired quantizer allocations. Generally, we must expect to find more than one process $y$ satisfying this definition. Application of the criterion of efficiency thus serves only to eliminate a set of clearly wasteful modes of bit allocation, leaving us with a set of efficient points from which further choice by other criteria is to be made.

The third element of the bit allocation analysis is a theorem which, following [3], allows to characterize the concept of ``efficient allocation process'' by maximization of $p \cdot y$ with respect to $y$ over $Y$, for some vector $p$. An interesting interpretation can be given to vector $p$ on an efficient point $\hat{y}$. We shall call the (m+1)-tuple $p$ a profit vector of the quantizer-based allocations in the efficient point $\hat{y}$:

$$p = ( p_1, \cdots, p_m, p_{m+1})^T,$$

where $p_j$ denotes the profit per bit for quantizer $Q_j$, with $j=1, \cdots, m$; and $p_{m+1}$ denotes the price per bit for bit consumption. The expression $p \cdot y$ is now interpreted as the profit from allocation process $y$.

Theorem 1: Characterization of Efficient Allocation Process. Let $Y$ be a convex set of allocation processes. If $\hat{y}$ is an efficient allocation process of $Y$ then there exists a (m+1)-tuple $p \geq 0$, $\vert\vert p \vert\vert < \infty$ such that $\hat{y}$ maximizes the profit $p \cdot y$ from an allocation process, with respect to $y$ over $Y$.

Proof. Let $X = Y - \hat{y}$, then $X$ is convex as it is a linear sum of two convex sets, [4].

Also, let $\Omega^0$ be the positive orthant of (m+1)-dimensions (that is, the analogue of a quadrant in the plane, which is defined by a system of inequalities in geometry of (m+1)-dimensions).

Then we have that $X$ and $\Omega^0$ are two disjoint nonempty convex sets since $X \cap \Omega^0 = \emptyset$. If it is not true, there exists a $z > 0$ such that $z \in (Y - \hat{y}) \cap \Omega^0$. It follows that $z + \hat{y} \in Y$ and thus $\hat{y}$ is not an efficient allocation of $Y$, which is a contradiction.

Hence, following the Minkowski's Theorem, [5], there exists a $p \not= 0$, $\vert\vert p \vert\vert < \infty$, and $\alpha \in R$ such that

$$p \cdot z \stackrel{>}{=} \alpha, \mbox{ and, } p \cdot x \st... ...el{<}{=} \alpha, \ \mbox{ for all } z \in \Omega^0, \ x \in X.$$

It asserts the existence of a hyperplane that separates two disjoint convex sets, which is probably the most fundamental theorem in the mathematical theory of optimization.

We have that $\alpha \stackrel{>}{=} 0$ since $0 \in X$ for $\hat{y} \in Y$. Then, $p \geq 0$. In other case, there exists a negative element of $p$, since $p \not= 0$. By choosing the corresponding element of $z$ large enough, it follows $p \cdot z < 0$ which is a contradiction.

But also $\alpha \stackrel{<}{=} 0$ since, in other case, $p \cdot z \stackrel{>}{=} \alpha > 0$ for all $z \in \Omega^0$ and therefore we can have $p \cdot z < \alpha$ choosing $\vert\vert z\vert\vert$ small enough, which is a contradiction.

From $\alpha \stackrel{>}{=} 0$ and $\alpha \stackrel{<}{=} 0$ it follows that $\alpha = 0$. Hence, we have that $p \cdot x \stackrel{<}{=} 0$ for all $x \in X$ with $p \geq 0$ which concludes the proof, since there exists a profit vector $p \geq 0$, $\vert\vert p \vert\vert < \infty$ such that $p \cdot \hat{y} \stackrel{>}{=} p \cdot y, \ \mbox{ for all } y \in Y. \ \ \ {\bf\Box}$

If there exists a $p > 0$, $\vert\vert p \vert\vert < \infty$ such that $p \cdot \hat{y} \stackrel{>}{=} p \cdot y, \ \mbox{ for all } y \in Y$, then $\hat{y}$ is an efficient allocation process of $Y$. In other case, there exists a $y \in Y$ such that $y \geq \hat{y}$ and, since $p > 0$, we have that $p \cdot y > p \cdot \hat{y}$, which is a contradiction.