Assign vectors binary encodings based on dot product

Question

I have a set of $n$ normalized vectors and I would like to assign each to a unique binary encoded representation of length $log(n)$. I want to find an assignment such that vector pairs with higher dot products have smaller hamming distances in the binary encoding representation and vectors with smaller dot products will have larger hamming distances in the binary encoding representation.

Ex: given 3 vectors ${v_1 , v_2 , v_3}$ from a set of $n = 4$ vectors. If $v_1 \cdot v_2 = .1$ , $v_1 \cdot v_3 = .2$, and $v_2 \cdot v_3 = .8$

Possible assignment could be $v_1 = 00$ $v_2 = 11$ $v_3 = 10$

$v_1$ and $v_2$ have the lowest dot product and thus have a hamming distance of 2 and $v_2$ and $v_3$ are close so their hamming distance is 1.

Obviously this is not a perfect example but would extend better hopefully into larger dimensions. I'm struggling to solve this problem let alone formulate a concrete objective to solve for. The point is just to keep higher dot product vectors within a smaller hamming distance in the binary encoding. Any help formulating a proper objective and a solution would be awesome!

Answer 1

Here's a wacky idea, but I think it might work. It's about 40% of the way there. First and foremost, it only (for now) works for vectors in the all-positive octant.

First, for a large integer $N$, convert numbers between $0$ and $1$ to ints between $0$ and $N$ by multiplying by $N/2$, and rounding. Let's call this $x \mapsto U(x)$.

Now for a k-bit representation of a nonnegative integer, produce a $2^k$-bit represention by copying the 1's bit, making 2 copies of the 2's bit, making 4 copies of the 4's bit, and so on. So

101 --> 1111001

Call this $n \mapsto E(n)$, for "expand".

Hold off on picking $N$ for a moment, but suppose we've done so. In fact, suppose $N = 2^p$.

Now, for a vector $$\pmatrix{x\\y\\z},$$ write down $$\pmatrix{E(U(x))\\ E(U(y))\\ E(U(z))}$$.

The three entries in this vector will be bit-strings of length $2^{2^p}$, and we can concatenate them to get a single, even longer, bitstring.

The "dot" product of two such representations is, roughly, proportional to the dot product of the two vectors represented. (The approximation improves as $N$ gets large). [It might take some work to see this...]

For such a dot-product to be large, we need $1$s in exactly the same locations in the vectors, hence we have a small hamming distance, and vice-versa.