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!


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

  • $\begingroup$ Thanks for the response John! That was a super interesting idea. I apologize for not having fully defined the problem but I was hoping for binary representations with log(N) bits. The overall objective for this to me is too compress the vectors into a smaller space while maintaining as much of the relative the properties of dot product between the compressed vectors from the original vector space. I'll adjust my question. I'm thinking that maybe there is a way to build on your idea! $\endgroup$
    Oct 7, 2020 at 21:20
  • $\begingroup$ Sigh. Again, sigh. $\endgroup$ Oct 7, 2020 at 21:22
  • $\begingroup$ I'm so sorry for that. I appreciate all the effort that you put in. $\endgroup$
    Oct 7, 2020 at 21:24
  • 1
    $\begingroup$ Nah... I was sighing at myself. Often new folks leave something critical out of their questions, and I'm usually wise enough to make a few probing comments before answering the clarified question. I fell into the trap of thinking I had a cool idea and answered without asking for clarification, and now you've edited the question, which makes my answer look as if I'm an idiot who doesn't read questions before answering. I can live with that (although as a general tip: it costs nothing to ask a new question, where you add the conditions you intended, but if a bunch of people have answered ... $\endgroup$ Oct 7, 2020 at 21:32
  • $\begingroup$ ...it does cost some goodwill if you change the question later.) I actually appreciated the chance to think about fun encodings for a moment, even if it was a wasteful encoding. $\endgroup$ Oct 7, 2020 at 21:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .