1
$\begingroup$

Suppose I have a matrix $A$ with its entry $A_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that the Hamming distance between code word for $i$ and $j$ is (roughly) proportional to $A_{ij}$?

A related question is that given a set of points, design a binary code where the Hamming distance is (roughly) proportional to the Euclidean distance.

$\endgroup$
1
$\begingroup$

This is known as an embedding into $\{0,1\}^n$. Your matrix $A$ defines a weighted graph, and you want an embedding into the hypercube.

I suggest you examine the literature on low-distortion graph embeddings, which have been studied in great depth in the computer science literature. You might find some existing constructions on this topic. I'm not deeply familiar with that literature myself and I don't know whether you will find anything directly applicable.

$\endgroup$
  • $\begingroup$ Hm, this is just on the border between comment and answer (good pointer but not much of an answer in itself). Some more meat would be good, imho. $\endgroup$ – Raphael Aug 15 '14 at 7:36
  • $\begingroup$ @Raphael, I figured that sometimes "here's how to answer your question yourself" can still be helpful, particularly when no one else seems to know the answer off the top of their head. I agree more meat would be nice to have, but this is all I've got right now. I'm going to leave it up to the author to do the heavy lifting of spending a few days in the library reviewing related literature -- that's more than I can take on right now. $\endgroup$ – D.W. Aug 15 '14 at 14:56
  • $\begingroup$ I see; it's not clear from the answer that you don't know (much) more than the keywords myself. $\endgroup$ – Raphael Aug 15 '14 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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