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$)


$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)$


$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$.

No comments:

Post a Comment