Saturday, September 24, 2011

Investigating Quantization Cells


How to investigate the cells from the quantizer/encoder ${\rm round}_\mathbb{Z} \tilde{E}$ where $\tilde{E}$ is $m \times N$ on the set $X$ from before ($1 \geq |x_{(1)}| \geq 2|x_{(2)}| \geq \ldots \geq N|x_{(N)}|$)

In any case, need to cover our set X with the quantization cells.

Are the cells concentrated near the axes?

Is there any experiment I can run?
First study the signal on the boundary:

  1. Take random permutation $P$ and signs $\xi$
  2. Set $x(P(i)) = \xi(i)/i$ 

 First question: Can I determine what cell it is in, and what the size is? $q = {\rm round}_\mathbb{Z}\tilde{E} x$. What other signals in $X$?

Next question: What properties must $\tilde{E}$ have for the cell to be small?


 How to determine the set of all signals that map to this $q$?

 The region of measurements that rounds to $q$ we know...  $<e_i,x> = q_i \pm 0.5$ where $e_i$ are the entries of $\tilde{E}$. How about the inverse image of this region? Some notes:

  • It's a convex region, and a linear transformation, so we only need to map the endpoints ($2^m$ of them), and take the convex hull.
  • For any given measurement, the preimage under $\tilde{E}$ is a $N-m$ dimensional subspace (assume $\tilde{E}$ is full rank), which we then need to intersect with $X$.

This seems like quite the daunting task...

Tuesday, September 6, 2011

More on Toy Problem

Continuing from last time, we had this picture:

(there should be one of these cross-shaped structures on every axis). An encoding scheme based off of such a 2D projection would be to cover the 2D image with balls of a suitable radius (or potentially different radii, depending on the thickness in the orthogonal direction in 3D), and round to the nearest ball center to encode. Then to recover, convert the ball center to the set of corresponding line of 3D coordinates and choose the center.

If we use a fixed radius $r$, and the max thickness in the other dimension is $T$, then the distortion at worst will be $\sqrt{r^2 + (T/2)^2}$.

Idea:  (not quite true, but almost true)  Because of the special nature of the set (star-shaped), the thickness also behaves in a similarly-nice way:   If the thickness at the 2d projection is $T(x,y)$, then $T(rx,ry) = rT(x,y)$ (thickness is homogenous). Thus, if we just cover the bow-tie face first, we can figure out how to reduce the encoding radius of the ball as we approach the origin. Then we can study the properties of the rate distortion curve with this encoding method....

By symmetry considerations a guess for a good projection angle is $(1,1,1)/\sqrt{3}$ (using a basis for the orthogonal complement to project onto).
Thus $(1,1/2,1/3) = (11,11,11)/18 + (7,-2,-5)/18$ is mapped to $(7,-2,-5)/18$. We can additionally place a coordinate axis on the grid by using an orthogonal basis for the projection plane, but we will not need that now.

As an example computation, we can compute the thickness of how many points are mapped to this same point, at least the ones in the same convex region.

Consider the point $x=(1,1/2,1/3)$, and we use the projection direction $(1,1,1)$. We can first focus on the region containing $x$ defined by the inequalities $1 \geq x_1 \geq 2x_2 \geq 3x_3$ and $x_i \geq 0$. How far along $(1,1,1)$ can we travel  until we escape this region? We find the minimal $t>0$ for which one of the inequalities becomes equality (looking at $x - t(1,1,1)$):

$1 - t = 1,  1 - t = 2(1/2 - t), 2(1/2 - t) = 3(1/3 - t)$  (all $t=0$)

and

$1 - t = 0,  1/2 - t = 0, 1/3 - t = 0$

The minimal $t$ from above is $t=1/3$, which brings us to the point $(2/3,1/6,0)$. Now we are in the region where $x_3 < 0$, so the bounding inequalities become $1 \geq x_1 \geq 2x_2 \geq -3x_3$ and $x_1,x_2 \geq 0,  x_3 \leq 0$. Again we solve for when we hit the boundary:

$2/3 - t = 1,  2/3-t = 2(1/6-t),  2(1/6-t)=-3(0-t)$

and

$2/3 - t = 0,  1/6 - t = 0, 0 - t = 0$

The minimal $t$ from above is now $t = 1/15$, when $2|x_2| = 3|x_3|$, at the point $(3/5,1/10,-1/15)$, and now we are outside the compressible region. Thus the thickness of the points mapping the same as $(1,1/2,1/3)$ is $2\sqrt{3}/5$.