2
$\begingroup$

I have a function on $h: [0,1] \to [0,1]$ whose output is smooth (polynomial of low degree), and I need to discretize it but I need to save it with three 8 bit numbers. These three 8 bit numbers need to be ok to interpolate, so basically the definition of Lipschitz continuity.

That is I want to find a way to store my $x\in [0,1]$ numbers as $f(x)\in 2^8 \times 2^8 \times 2^8$ and I would like:

$$|f(x_1)-f(x_2)| \leq K |x_1 - x_2|$$

With K not too large, and store as many $x$s as possible (I am interested in inverting this map later).

Now, I know how to do it with $K=3$ and for $2^8$: Just divide $[0,1]$ into $\{ \frac{1,2,...,256}{256} \}$ and have $f(x) \mapsto (256x,256x,256x)$.

The question is how much better can I do? Can I save $2^N$ $x$s with a small $K$ and large $N$? I know I could save $2^{24}$ if $K$ was huge, but I would like to find a middle ground.

As I understand the folding solution from another question will have a big $K$ in my case if we consider neighboring elements in the image of $f$ which cut across the folds.

$\endgroup$
2
  • 2
    $\begingroup$ Are you sure you want Lipschitz continuity? For $x$ continuous and $f(x)$ discrete, you are always going to have arbitrarily small changes in $x$ leading to changes in $f(x)$ (if $f$ is constant). Maybe you discretize $x$ before checking the Lipschitz condition, but then it only depends on $| f(x + 1/2^N) - f(x)|$. A Holder continuity condition might be more useful here because it forces $f(x_1)$ to stay close to $f(x_2)$ for longer. If you were saving $x$ into two numbers instead of three, would a Hilbert curve (en.wikipedia.org/wiki/Hilbert_curve) be what you want? $\endgroup$
    – Will Sawin
    Jan 31, 2021 at 15:16
  • $\begingroup$ @WillSawin Good suggestion about the Hilbert curves! I've added some colormaps from 3D Hilbert Curves in my answer $\endgroup$
    – polpetti
    Feb 2, 2021 at 4:34

1 Answer 1

0
$\begingroup$

I realize now that this question is analogous to asking to fit an ordered set of $2^N$ discrete points into a cube of discrete points with size $2^8 \times 2^8 \times 2^8$. The discrete points will snake around in this cube (they can't be scattered because that will make the Libschitz constant of $f:2^N \to 2^8 \times 2^8 \times 2^8$ large).

Looking at how matplotlib's HSV colormap clarified this. matplotlib's HSV cmap maps $[0,1] \to 2^8 \times 2^8 \times 2^8$, and really in implementation it maps $2^8 \to 2^8 \times 2^8 \times 2^8$ because their code uses a lookuptable with size 256. The way it maps the unit interval to RGB is like so:

enter image description here

This means on the $2^8 \times 2^8 \times 2^8$ cube we can snake a $6\times 2^8$ long line across the edges in a loop like so, starting and ending at the black dot:

enter image description here

For this particular mapping that covers 6 edges, it can store 8 bits of information 6 times. So $N\approx 10.58$ and $K = 6$. We could easily think of extending this loop to 8 faces without our path crossing, then $N=11$ and $K=8$.

And you can go further, snaking around a longer and longer line. So the relationship becomes clear:

For an injective mapping $f: 2^N \to 2^8 \times 2^8 \times 2^8$ with Lipschitz-1 bound $K$, $K$ and $N$ are not independent. If $N=8$, $K=1$ which is small, but if $N=24$, $K$ must be large. In fact as far as I understand for $N\geq 8$, $K=2^{N-8}$.

To fit a lot of bits into a colormap, your colors must change fast when you draw the colormap for the unit interval.

The HSV colormap with its 10.58 bits looks like:

enter image description here

But a colormap where Red stores the 8 most significant bits, Green the 8 middle significant bits, and Blue the 8 least significant bits, of a 24 bit fixed point number in $[0,1]$ looks like:

enter image description here

This means if you have a collection of data that you need to encode into a sequence of colors, and you expect some small noise added to each color channel before inverting back to the original data format, you will not be able to invert with to the original noiseless data with anywhere near $2^{24}$ bits precision.

Following @Will Sawin's answer, we can draw a Hilbert curve in $2^8 \times 2^8 \times 2^8$ space to make the colormap, with more subcubes leading to a longer curve. For 3 subcubes per side this looks like:

enter image description here

This image is from here where there is also code to generate these paths. I've included the colormaps for 1,2,3, and 4 subcubes per side:

enter image description here

Plotting the RGB of these paths makes the paths clearer:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.