# Is this some kind of hashing?

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?

• 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. – Nicholas Mancuso Apr 22 '16 at 23:00