2
$\begingroup$

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?

$\endgroup$
  • $\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 '18 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$ – felipa Mar 3 '18 at 18:42
2
$\begingroup$

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.

$\endgroup$
  • $\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$ – Lembik Mar 15 '18 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$ – Lembik Mar 15 '18 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 '18 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$ – Anush Aug 2 '18 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 '18 at 15:55

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.