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?

  • $\begingroup$ The article you link suggests to use the "Pearson's distance" for clustering. Is this sufficient for your purposes? If not, why? $\endgroup$
    – Discrete lizard
    Mar 3, 2018 at 18:13
  • $\begingroup$ @Discretelizard If there is a linearish time algorithm for clustering using the Pearson distance that would be very interesting. I really want to find the $n$ closest neighbors to each vector. $\endgroup$
    – Simd
    Mar 3, 2018 at 18:42

1 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.

  • $\begingroup$ What do you do for a vector (1,1)? If you subtract the mean you get the zero vector and then s is 0. $\endgroup$
    – Simd
    Mar 15, 2018 at 8:55
  • $\begingroup$ I may be a little confused, apologies. If you literally take the mean from (1,1) you get (0,0) and so the normalized vector does not have length 1. What should the mapped version of (1,1) be according to your formula? $\endgroup$
    – Simd
    Mar 15, 2018 at 18:27
  • $\begingroup$ @Lembik, Ahh, now I understand what you are saying. Thanks for explaining so patiently. My fault. OK, I've revised the answer. Now I think it addresses your point (and corrects an error in the previous version of my answer). Does that answer your question? $\endgroup$
    – D.W.
    Mar 15, 2018 at 18:33
  • $\begingroup$ If you just subtract the mean and then divide by the standard deviation, you get a vector of $L_2$ norm $\sqrt{n}$. You need to divide the vector by $\sqrt{n}$ to get a norm of $1$ don't you? $\endgroup$
    – Simd
    Aug 2, 2018 at 10:23
  • 1
    $\begingroup$ @Anush, $s$ isn't the standard deviation. Suppose $v=(3,-3)$; then $s=3\sqrt{2}$, so $\tilde{v}=(1/\sqrt{2},-1/\sqrt{2})$ and then $\|\tilde{v}\|=1$. Yes, if we divided by the standard deviation, we'd then have to divide by $\sqrt{n}$; but my $s$ is $\sqrt{n}$ times the standard deviation, so dividing by $s$ is equivalent to that. $\endgroup$
    – D.W.
    Aug 2, 2018 at 15:55

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.