# Z-Normalized Euclidean Distance Derivation

I am going through this paper:

http://www.cs.ucr.edu/~eamonn/PID4481997_extend_Matrix%20Profile_I.pdf

And on Page 4, it is claimed that the squared z-normalized euclidean distance between two vectors of equal length, Q and T[i], (the latter of which is just the ith subsequence of a longer 1D array, T) can be calculated from:

Here, m is the length of Q (or T[i]), mu_Q is the mean of Q, M_T[i] is the mean for the ith subsequence of T, sigma_Q is the standard deviation of Q, sigma_T[i] is the standard deviation for the ith subsequence of T, and Q.T[i] is the dot product between Q and T[i].

I am attempting to derive this equation from first principals but can't see to reconcile the final steps:

In this case, the summation loops through each element of either T[i] or Q. Also, recall that:

I've gotten as close as this but it's not quite right:

A semi-related question is here.

• I hate to say it, but 99% of your problem seems to stem from a truly awful notation (for which we may blame the paper, evidently). This algebra has been done over and over again in literally hundreds of posts here: it comes down to the fact that the sum of the residuals relative to the mean is zero. – whuber Mar 9 '17 at 22:20
• Would you mind pointing me to one of the hundreds of posts that demonstrates that logic? I've searched for a week and haven't come across anything remotely close. – slaw Mar 10 '17 at 2:48

I research the MP paper 1 and 2. And I know your pain !!

• Your second to the last step is wrong. After evaluating the average value you should drop the "sum" symbol in your equation. That's why you got an extra m. – newpigpig May 18 '17 at 8:06
• My steps are equivalent to the below [ Here's a straightforward way. ] I prove that [ (d_i,j)^2 = ~ ] not [ (d_i,j) = ~ ]. If you read the matrix profile paper carefully and know the dot product between subsequences [ t_i+k ] and [ t_j+k ] , you will know your point is wrong. – Sky Woo Sep 21 '19 at 13:48
• In case others stumble across this, the STUMPY Python library now offers an efficient implementation for computing matrix profiles stumpy.readthedocs.io/en/latest (along with other tools in that ecosystem) – slaw Jan 9 '20 at 16:28
• I have seen the python library, too. – Sky Woo Jan 11 '20 at 17:57

Here's a straightforward way. Let $\mathbf u$ and $\mathbf v$ be $m$-vectors.

Let $\mu_1=\frac 1m\sum_{k=1}^m u_k$ and $\mu_2=\frac 1m\sum_{k=1}^m v_k$ denote their means.

Let $\sigma_1^2=\frac 1m\sum_{k=1}^m (u_k-\mu_1)^2$ and $\sigma_2^2=\frac 1m\sum_{k=1}^m (v_k-\mu_2)^2$ denote their standard deviations. This rewrites as $\sigma_1^2=\frac 1m\left|\left| \mathbf u-\mu_1\mathbf 1 \right| \right|^2$, hence $m=\left| \left| \frac{\mathbf u-\mu_1\mathbf 1}{\sigma_1} \right| \right|^2=\left| \left| \frac{\mathbf v-\mu_2\mathbf 1}{\sigma_2} \right| \right|^2$

The squared $z$-normalized Euclidean distance between $\mathbf u$ and $\mathbf v$ is \begin{align}\left|\left|\frac{\mathbf u-\mu_1\mathbf 1}{\sigma_1} -\frac{\mathbf v-\mu_2\mathbf 1}{\sigma_2}\right|\right|^2 &= \left| \left| \frac{\mathbf u-\mu_1\mathbf 1}{\sigma_1} \right| \right|^2+\left| \left| \frac{\mathbf v-\mu_2\mathbf 1}{\sigma_2} \right| \right|^2 -\frac{2}{\sigma_1 \sigma_2} \langle \mathbf u-\mu_1\mathbf 1, \mathbf v-\mu_2\mathbf 1\rangle \\ &= 2m-\frac{2}{\sigma_1 \sigma_2} \left(\langle \mathbf u,\mathbf v \rangle-\mu_2 \sum_{k=1}^mu_k -\mu_1 \sum_{k=1}^mv_k + \mu_1 \mu_2m \right)\\ &=2m-\frac{2}{\sigma_1 \sigma_2} \left(\langle \mathbf u,\mathbf v\rangle -\mu_2m\mu_1 - \mu_1m\mu_2+\mu_1 \mu_2m \right)\\ &=2m \left(1-\frac{1}{m\sigma_1 \sigma_2}\left(\langle \mathbf u,\mathbf v\rangle -m\mu_1\mu_2\right) \right) \end{align}

• Lmao at the downvote... – Gabriel Romon Jun 20 '19 at 19:12