Constrained quantization for the Cantor distribution

Real-life problems, such as information theory, data compression, signal processing, etc., consist of a large number of data that is not easy to handle. In order to deal with such a data set, the theory of quantization comes into play (see, for instance, [1, 2, 3, 4, 5, 6, 7]). Quantization is a process of discretization, in other words, to represent a set with a large number of elements, discrete or continuous, by a set with a smaller number of elements. Several mathematical theories have been introduced in the literature concerning the process of quantization. Graf and Luschgy gave the rigorous mathematical treatment in [2]. In [8], Graf and Luschgy studied the quantization problem for the canonical probability measure on the classical Cantor set.

Recently, in [9], the authors introduced the concept of constrained quantization. A quantization without a constraint is referred to as an unconstrained quantization, which traditionally in the literature is referred to as a quantization, as mentioned in the previous paragraph. The theory of constrained quantization is a fascinating area of research, and it invites a lot of new areas to work with a number of applications. With the introduction of constrained quantization, quantization now has two classifications: constrained quantization and unconstrained quantization. In this paper, the authors have further generalized the definition of constrained quantization given in [9], and study the concept of constrained quantization for the canonical probability measure on the classical Cantor set.

The number

is called the distortion error for $P$, of order $r$, with respect to a set $\alpha\subseteq\mathbb{R}^{k}$. The sets $S_{j}$ are the constraints in the constrained quantization error. We assume that $\int d(x,0)^{r}dP(x)<\infty$ to make sure that the infimum in (1) exists (see [9]). A set $\alpha\subseteq\mathop{\bigcup}\limits_{j=1}^{n}S_{j}$ for which the infimum in (1) exists and does not contain more than $n$ elements is called an optimal set of $n$-points for $P$. Elements of an optimal set are called optimal elements.

Let $V_{n,r}(P)$ be a strictly decreasing sequence, and write $V_{\infty,r}(P):=\mathop{\lim}\limits_{n\to\infty}V_{n,r}(P)$. Then, the number $D_{r}(P)$ defined by

if it exists, is called the constrained quantization dimension of $P$ of order $r$. The constrained quantization dimension measures the speed at which the specified measure of the constrained quantization error converges as $n$ tends to infinity. For any $\kappa>0$, the number

if it exists, is called the $\kappa$-dimensional constrained quantization coefficient for $P$ of order $r$.

This paper deals with $r=2$ and $k=2$, and the metric on $\mathbb{R}^{2}$ as the Euclidean metric induced by the Euclidean norm $\lVert\cdot\rVert$. Instead of writing $V_{r}(P;\alpha)$ and $V_{n,r}:=V_{n,r}(P)$ we will write them as $V(P;\alpha)$ and $V_{n}:=V_{n}(P)$, i.e., $r$ is omitted in the subscript as $r=2$ throughout the paper. Let us take the family $\{S_{j}:j\in\mathbb{N}\}$, that occurs in Definition 1.1 as follows:

Let $T_{1},T_{2}:\mathbb{R}\to\mathbb{R}$ be two contractive similarity mappings such that $T_{1}(x)=\frac{1}{3}x$ and $T_{2}(x)=\frac{1}{3}x+\frac{2}{3}$. Then, there exists a unique Borel probability measure $P$ on $\mathbb{R}$ such that $P=\frac{1}{2}P\circ T_{1}^{-1}+\frac{1}{2}P\circ T_{2}^{-1}$, where $P\circ T_{i}^{-1}$ denote the image measures of $P$ with respect to $T_{i}$ for $i=1,2$ (see [21]). If $k\in\mathbb{N}$, and $\sigma:=\sigma_{1}\sigma_{2}\cdots\sigma_{k}\in\{1,2\}^{k}$, then we call $\sigma$ a word of length $k$ over the alphabet $I:=\{1,2\}$, and denote it by $|\sigma|:=k$. By $I^{\ast}$, we denote the set of all words, including the empty word $\emptyset$. Notice that the empty word has a length zero. For any word $\sigma:=\sigma_{1}\sigma_{2}\cdots\sigma_{k}\in I^{\ast}$, we write

Then, the set $C:=\bigcap_{k\in\mathbb{N}}\bigcup_{\sigma\in\{1,2\}^{k}}J_{\sigma}$ is known as the Cantor set generated by the two mappings $T_{1}$ and $T_{2}$, and equals the support of the probability measure $P$, where $P$ can be written as

For this probability measure $P$, Graf and Luschgy determined the optimal sets of $n$-means and the $n$th quantization errors for all $n\in\mathbb{N}$ (see [8]). They also showed that the unconstrained quantization dimension of the measure $P$ exists and equals $\frac{\log 2}{\log 3}$, which is the Hausdorff dimension of the Cantor set $C$, and the unconstrained quantization coefficient does not exist. In fact, in [8], they showed that the lower and the upper unconstrained quantization coefficients exist as finite positive numbers.

In this section, we give some basic notations and definitions which we have used throughout the paper. As defined in the previous section, let $I:=\{1,2\}$ be an alphabet. For any two words $\sigma:=\sigma_{1}\sigma_{2}\cdots\sigma_{k}$ and $\tau:=\tau_{1}\tau_{2}\cdots\tau_{\ell}$ in $I^{*}$, by $\sigma\tau:=\sigma_{1}\cdots\sigma_{k}\tau_{1}\cdots\tau_{\ell}$, we mean the word obtained from the concatenation of the two words $\sigma$ and $\tau$. For $\sigma,\tau\in I^{\ast}$, $\sigma$ is called an extension of $\tau$ if $\sigma=\tau x$ for some word $x\in I^{\ast}$. The mappings $T_{i}:\mathbb{R}\to\mathbb{R},\ i=1,2,$ such that $T_{1}(x)=\frac{1}{3}x$ and $T_{2}(x)=\frac{1}{3}x+\frac{2}{3}$ are the generating maps of the Cantor set $C$, which is the support of the probability measure $P$ on $\mathbb{R}$ given by $P=\frac{1}{2}P\circ T_{1}^{-1}+\frac{1}{2}P\circ T_{2}^{-1}$. For $\sigma:=\sigma_{1}\sigma_{2}\cdots\sigma_{k}\in I^{k}$, write $J_{\sigma}=T_{\sigma}[0,1]$, where $T_{\sigma}:=T_{\sigma_{1}}\circ T_{\sigma_{2}}\circ\cdots\circ T_{\sigma_{k}}$ is a composition mapping. Notice that $J:=J_{\emptyset}=T_{\emptyset}[0,1]=[0,1]$. Then, for any $k\in\mathbb{N}$, as mentioned before, we have

The elements of the set $\{J_{\sigma}:\sigma\in I^{k}\}$ are the $2^{k}$ intervals in the $k$th level in the construction of the Cantor set $C$, and are known as the basic intervals at the $k$th level. The intervals $J_{\sigma 1}$, $J_{\sigma 2}$, into which $J_{\sigma}$ is split up at the $(k+1)$th level are called the children of $J_{\sigma}$.

With respect to a finite set $\alpha\subset\mathbb{R}^{2}$, by the Voronoi region of an element $a\in\alpha$, it is meant the set of all elements in $\mathbb{R}^{2}$ which are nearest to $a$ among all the elements in $\alpha$, and is denoted by $M(a|\alpha)$. For any two elements $(a,b)$ and $(c,d)$ in $\mathbb{R}^{2}$, we write

which gives the squared Euclidean distance between the two elements $(a,b)$ and $(c,d)$. Let $p$ and $q$ be two elements that belong to an optimal set of $n$-points for some positive integer $n$. Then, $p$ and $q$ are called adjacent elements if they have a common boundary in their own Voronoi regions. Let $e$ be an element on the common boundary of the Voronoi regions of the adjacent elements $p$ and $q$. Since the common boundary of the Voronoi regions of any two adjacent elements is the perpendicular bisector of the line segment joining the elements, we have

We call such an equation a canonical equation. Notice that any element $x\in\mathbb{R}$ can be identified as an element $(x,0)\in\mathbb{R}^{2}$. Thus, the nonnegative real-valued function $\rho$ on $\mathbb{R}\times\mathbb{R}^{2}$ defined by

represents the squared Euclidean distance between an element $x\in\mathbb{R}$ and an element $(a,b)\in\mathbb{R}^{2}$. Let $\pi:\mathbb{R}^{2}\to\mathbb{R}$ such that $\pi(a,b)=a$ for any $(a,b)\in\mathbb{R}^{2}$ denote the projection mapping. For a random variable $X$ with distribution $P$, let $E(X)$ represent the expected value, and $V:=V(X)$ represent the variance of $X$.

The following lemmas are well-known (see [8]).

In the next sections, we give the main results of the paper.

In this section, we calculate the optimal sets of $n$-points and the $n$th constrained quantization errors for all $n\in\mathbb{N}$. For $j\in\mathbb{N}$, we have the constraints as

For all $j\in\mathbb{N}$, the perpendiculars on the constraints $S_{j}$ passing through the points $(a,\frac{1}{j})\in S_{j}$ intersect $J$ at the points $a$, where $0\leq a\leq 1$. Thus, for each $j\in\mathbb{N}$, there exists a one-one correspondence between the element $(a,\frac{1}{j})$ on $S_{j}$ and the element $a$ on $J$. Thus, for $j\in\mathbb{N}$, there exist bijective functions

Hence, the inverse functions $U_{j}^{-1}$ are defined as

The following lemma plays an important role in the paper.