How to embed Pearson distance into Euclidean space

Question

I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time and too slow. Ideally I would like to be able to perform efficient approximate nearest neighbour searches instead.

If I could embed the vectors into Euclidean space then I could use standard tools to do this.

Is there a way to embed vectors from a space using the Pearson distance into Euclidean space?

Answer 1

Yes. Normalize the vectors, then use the Euclidean ($L_2$) distance.

In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector

$$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$

where $\mu=(v_1+\dots+v_n)/n$ is the mean of the elements and $s=\sqrt{(v_1-\mu)^2 + \dots + (v_n-\mu)^2}$. (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\dots,1/\sqrt{n})$.) Then the vector $\tilde{v}$ has unit length.

Now the Pearson distance $d_P$ satisfies

$$d_P(u,v) = 1 - \tilde{u} \cdot \tilde{v} = \|\tilde{u} - \tilde{v}\|^2 / 2,$$

where $\|\cdot\|$ is the Euclidean ($L_2)$ norm. (See here and here for a derivation of the above equation.)

Thus, minimizing the Pearson distance between $u,v$ is equivalent to minimizing the Euclidean distance between $\tilde{u},\tilde{v}$. So once you've mapped vector $v$ to its embedding $\tilde{v}$, you can use a standard nearest neighbor data structure (with Euclidean distance) to answer nearest neighbor searches.