# 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, 2017 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, 2017 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. May 18, 2017 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. Sep 21, 2019 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, 2020 at 16:28
• I have seen the python library, too. Jan 11, 2020 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... Jun 20, 2019 at 19:12