Say I have $n$ vectors $\{ z_i \in \mathbb{R}^D\}_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\{x_i \in \mathbb{R}^d \}_{i=1}^n$ with $d$ as small as possible, such that $\forall i,j <z_i,z_j>$ is either very close to $<x_i,x_j>$ OR w.h.p $ <z_i,z_j> = <x_i,x_j>$.

  • Is there a standard answer known for this - by maybe using hashing?

  • One possible way might be to either deterministically or randomly from some distribution pick some $D-d$ coordinates and drop those coordinates from each $x_i$ to get the corresponding $z_i$ such that for each pair on either side either the inner-product is well approximated or is equal with high-probability over the way the coordinates are sampled. Is such a way of sampling known?

For the second option one other way to think would be to pick an unit magnitude gaussian vector at random $g \in \mathbb{R}^d \subset \mathbb{R}^D$ and to define $x_i$ as the projection of $z_i$ along $g$. Then indeed one has that $\mathbb{E}_g[ <x_i,x_j>] = <z_i,z_j>$.

But can this above be shown to be true with high concentration or be derandomized?

  • $\begingroup$ I'm not an expert in this matter, but I am aware of the Johnson-Lindenstrauss lemma which gives guarantees similar to what you demand. I would post as an answer, but I honestly am not familiar enough with the inner workings to warrant a complete post. $\endgroup$ – Nicholas Mancuso Apr 22 '16 at 23:00

I think your "possible way" is a known variant of "locality sensitive hashing", which is what you're looking for, I suspect.

| cite | improve this answer | |
  • $\begingroup$ The "standard" LSH references I see do not seem to fit my question. So I am asking what is this "varant" that jbapple refers to. Unless something more specific is said, I don't know what to search for! $\endgroup$ – gradstudent Apr 19 '16 at 6:09
  • $\begingroup$ @gradstudent, the method of dropping vector components is referenced in the first paper on LSH. $\endgroup$ – jbapple Apr 19 '16 at 14:11
  • $\begingroup$ You mean somewhere in this paper? cs.princeton.edu/courses/archive/spring13/cos598C/Gionis.pdf Are they able to preserve all pair-wise inner-products of any arbitrary set of vectors? $\endgroup$ – gradstudent Apr 19 '16 at 14:46

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.