5
$\begingroup$

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:

enter image description here

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:

enter image description here

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

enter image description here

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

enter image description here

A semi-related question is here.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – whuber Mar 9 '17 at 22:20
  • 1
    $\begingroup$ 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. $\endgroup$ – slaw Mar 10 '17 at 2:48
-1
$\begingroup$

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

enter image description here

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – newpigpig May 18 '17 at 8:06
  • $\begingroup$ 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. $\endgroup$ – Sky Woo Sep 21 '19 at 13:48
  • $\begingroup$ 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) $\endgroup$ – slaw Jan 9 at 16:28
  • $\begingroup$ I have seen the python library, too. $\endgroup$ – Sky Woo Jan 11 at 17:57
0
$\begingroup$

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} $$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Lmao at the downvote... $\endgroup$ – Gabriel Romon Jun 20 '19 at 19:12

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.