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$ Commented Apr 22, 2016 at 23:00

1 Answer 1


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

  • $\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$ Commented Apr 19, 2016 at 6:09
  • $\begingroup$ @gradstudent, the method of dropping vector components is referenced in the first paper on LSH. $\endgroup$
    – jbapple
    Commented Apr 19, 2016 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$ Commented Apr 19, 2016 at 14:46

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.