# Computing the Z-Normalized Euclidean Distance from Dot Products

In the [Matrix Profile I](https://www.cs.ucr.edu/~eamonn/STOMP_GPU_final_submission_camera_ready.pdf) and [Matrix Profile II](https://www.cs.ucr.edu/~eamonn/PID4481997_extend_Matrix%20Profile_I.pdf) papers, the Z-normalized Euclidean distance between a query subsequence, $Q_{i,m}=(q_i, q_{i+1}, q_{i+2}\ldots, q_{i+m-1})$, and the $i^{th}$ subsequence, $T_{i,m}=(t_i, t_{i+1}, t_{i+2}, \ldots, t_{i+m-1})$, with window size, $m$, in the time series, $T$, can be computed following:

\begin{align}
    D(Q_{i,m}, T_{i,m}) ={}&
        \sqrt{
            \sum \limits _{0 \leq {j} \lt m}
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    - 
                    \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                \right)^2
        }
    \\
    ={}&
        \sqrt{
            \sum \limits _{0 \leq {j} \lt m}
                \left[
                    \left(
                        \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    \right)
                    -
                    2
                    \left(
                        \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    \right)
                    \left(
                        \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                    \right)
                    +
                    \left(
                        \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                    \right)^2
                \right]
        }
    \\
    ={}&
        \sqrt{
            \sum \limits _{0 \leq {j} \lt m}
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                \right)^2
                -
            \sum \limits _{0 \leq {j} \lt m}
                2
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                \right)
                \left(
                    \frac{q_j-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                \right)
                +
            \sum \limits _{0 \leq {j} \lt m}
                \left(
                    \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                \right)^2
        }
    \\
    ={}&
        \sqrt{
            m
            -
            \sum \limits _{0 \leq {j} \lt m}
                2
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                \right)
                \left(
                    \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                \right)
            +
            m
        }
    \\
    ={}&
        \sqrt{
            2m
            -
            2
            \sum \limits _{0 \leq {j} \lt m}
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                \right)
                \left(
                    \frac{q_{i+j}-\mu_{Q_m}}{\sigma_{Q_{i,m}}}
                \right)
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{1}{m}
                \sum \limits _{0 \leq {j} \lt m}
                    \left(
                        \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    \right)
                    \left(
                        \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                    \right)
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \sum \limits _{0 \leq {j} \lt m}
                    \frac{
                        \left(
                            t_{i+j}-M_{T_{i,m}}
                        \right)
                        \left(
                            q_{i+j}-\mu_{Q_{i,m}}
                        \right)
                    }{
                        m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                    }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \sum \limits _{0 \leq {j} \lt m}
                    \frac{
                        t_{i+j}q_j
                        -t_{i+j}\mu_{Q_{i,m}}
                        -M_{T_{i,m}}q_{i+j}
                        +M_{T_{i,m}}\mu_{Q_{i+m}}
                    }{
                        m \sigma_{Q_{i+m}} \Sigma_{T_{i,m}}
                    }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    \sum \limits _{0 \leq {j} \lt m}
                        q_{i+j}t_{i+j}
                    -
                    \sum \limits _{0 \leq {j} \lt m}
                        t_{i+j}\mu_{Q_{i,m}}
                    -
                    \sum \limits _{0 \leq {j} \lt m}
                        \left(
                            M_{T_{i,m}}q_{i+j}
                            -M_{T_{i,m}}{\mu_{Q_{i,m}}}
                        \right)
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    Q_{i,m}\cdot{T_{i,m}}
                    -
                    \sum \limits _{0 \leq {j} \lt m}
                        t_{i+j}\mu_{Q_{i,m}}
                    -
                    M_{T_{i,m}}
                    \sum \limits _{0 \leq {j} \lt m}
                        \left(
                            q_{i+j}-{\mu_{Q_{i,m}}}
                        \right)
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    Q_{i,m}\cdot{T_{i,m}}
                    -
                    \mu_{Q_{i,m}}
                    \sum \limits _{0 \leq {j} \lt m}
                        t_{i+j}
                    -
                    0
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    Q_{i,m}\cdot{T_{i,m}}
                    -
                    \mu_{Q_{i,m}}
                    \sum \limits _{0 \leq {j} \lt m}
                        t_{i+j}
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    Q_{i,m}\cdot{T_{i,m}}
                    -
                    \mu_{Q{i,m}}m
                    \sum \limits _{0 \leq {j} \lt m}
                        \frac{t_{i+j}}{m}
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{
                    Q_{i,m}\cdot{T_{i,m}}
                    -
                    m\mu_{Q_{i,m}}M_{T_{i,m}}
                }{
                    m \sigma_{Q_{i,m}} \Sigma_{T_{i,m}}
                }
            \right]
        }
    \\        
\end{align}

# Computing the  Z-Normalized Euclidean Distance from the Pearson Correlation

Based on the fact that the Pearson Correlation, $\rho$, can be written as (see Equation 4 in [this paper](https://www.cs.unm.edu/~mueen/Projects/JOCOR/joinICDM.pdf) or Equation 3 in [this paper](https://arxiv.org/pdf/1601.02213.pdf)):

\begin{align}
    \rho(Q_{i,m}, T_{i,m}) ={}& \frac{E
        \left[
            \left(
                Q_{i,m}-\mu_{Q_{i,m}}
            \right)
            \left(
                T_{i,m}-M_{T_{i,m}}
            \right)
        \right]
    }{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
    \\
    ={}& 
        \frac{
            \langle
            \left(
                Q_{i,m}-\mu_{Q_{i,m}}
            \right)
            ,
            \left(
                T_{i,m}-M_{T_{i,m}}
            \right)
            \rangle
        }{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
    \\
    ={}&
        \frac{1}{m}
        \sum \limits _{0 \leq j \lt m}
            \frac{
                \left(
                    q_{i+j}-\mu_{Q_{i,m}}
                \right)
                \left(
                    t_{i+j}-M_{T_{i,m}}
                \right)
            }{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
    \\
    ={}&
        \frac{1}{m}
        \sum \limits _{0 \leq j \lt m}
            \left(
                \frac{
                    q_{i+j}-\mu_{Q_{i,m}}
                }{\sigma_{Q_{i,m}}}
            \right)
            \left(
                \frac{    
                    t_{i+j}-M_{T_{i,m}}
                }{\Sigma_{T_{i,m}}}
            \right)
    \\
\end{align}

Similar to above, the Z-normalized Euclidean distance can be computed from $\rho$ following:

\begin{align}
    D(Q_{i,m}, T_{i,m}) ={}&
        \sqrt{
            \sum \limits _{0 \leq {j} \lt m}
                \left(
                    \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    - 
                    \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                \right)^2
        }
        \\
    \vdots
        \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \frac{1}{m}
                \sum \limits _{0 \leq {j} \lt m}
                    \left(
                        \frac{t_{i+j}-M_{T_{i,m}}}{\Sigma_{T_{i,m}}}
                    \right)
                    \left(
                        \frac{q_{i+j}-\mu_{Q_{i,m}}}{\sigma_{Q_{i,m}}}
                    \right)
            \right]
        }
        \\
    ={}&
        \sqrt{
            2m
            \left[
                1
                -
                \rho(Q_{i,m},T_{i,m})
            \right]
        }
        \\
\end{align}

Thus, by employing the most efficient way to compute $\rho(Q_{i,m},T_{i,m})$, then we'd also have an efficient way to directly compute $D(Q_{i,m},T_{i,m})$. Recall that:

\begin{align}
    \rho(Q_{i,m},T_{i,m}) = \frac{cov(Q_{i,m},T_{i,m})}{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
\end{align}

Thus, it follows that finding the most efficient way to compute the covariance matrix, $cov(Q_{i,m},T_{i,m})$ would result in the most efficient way to compute the distance. Also, remember that we would like to traverse our distance matrix along each diagonal rather than along each row/column.

# Covariance

Recall that the covariance, $cov(Q_{i,m},T_{i,m})$, can be written as:

\begin{align}
    cov(Q_{i,m},T_{i,m}) ={}& E
        \left[
            \left(
                Q-\mu_{Q_{i,m}}
            \right)
            \left(
                T_{i,m}-M_{T_{i,m}}
            \right)
        \right]
    \\
    ={}& 
        \langle
            \left(
                Q-\mu_{Q_{i,m}}
            \right)
            ,
            \left(
                T_{i,m}-M_{T_{i,m}}
            \right)
        \rangle
    \\
    ={}&
        \frac{1}{m}
        \sum \limits _{0 \leq j \lt m}
            \left(
                q_{i+j}-\mu_{Q_{i,m}}
            \right)
            \left(
                t_{i+j}-M_{T_{i,m}}
            \right)
    \\
\end{align}

Note that we've explicitly called out the fact that the means, $\mu_{Q_{{i,m}}}$ and $M_{T_{i,m}}$, are computed with the subsequences of length $m$. Additionally, according to Welford, we can express these means with respect to the means of the same subsequences that have their last elements removed (i.e., $\mu_{Q_{i,m-1}}$ and $M_{T_{i,m-1}}$).

\begin{align}
    cov(Q_{i,m},T_{i,m}) 
    ={}&
        \frac{1}{m}
        \sum \limits _{0 \leq j \lt m}
            \left(
                q_{i+j}-\mu_{Q_{i,m}}
            \right)
            \left(
                t_{i+j}-M_{T_{i,m}}
            \right)
    \\
    ={}&
        \frac{
            S(Q_{i,m-1}, T_{i,m-1})
            +
            \left(
                \frac{m-1}{m}
            \right)        
            \left(
                q_{i+m-1} - \mu_{Q_{i,m-1}}
            \right)
            \left(
                t_{i+m-1} - M_{T_{i,m-1}}
            \right)
        }{m}
    \\
    ={}&
        \frac{
            \frac{m-1}{m-1}S(Q_{i,m-1}, T_{i,m-1})
            +
            \left(
                \frac{m-1}{m}
            \right)        
            \left(
                q_{i+m-1} - \mu_{Q_{i,m-1}}
            \right)
            \left(
                t_{i+m-1} - M_{T_{i,m-1}}
            \right)
        }{m}
    \\
    ={}&
        \frac{
            cov(Q_{i,m-1},T_{i,m-1}) (m-1)
            +
            \left(
                \frac{m-1}{m}
            \right)        
            \left(
                q_{i+m-1} - \mu_{Q_{i,m-1}}
            \right)
            \left(
                t_{i+m-1} - M_{T_{i,m-1}}
            \right)
        }{m}
    \\
    ={}&
        \frac{m-1}{m} 
        \left[
            cov(Q_{i,m-1},T_{i,m-1})
            +
            \frac{
                \left(
                    q_{i+m-1} - \mu_{Q_{i,m-1}}
                \right)
                \left(
                    t_{i+m-1} - M_{T_{i,m-1}}
                \right)
            }{m}
        \right]
    \\
\end{align}

Similarly, $cov(Q_{i-1,m},T_{i-1,m})$ can also be expressed with respect to $cov(Q_{i,m-1},T_{i,m-1})$:

\begin{align}
    cov(Q_{i-1,m},T_{i-1,m}) 
    ={}&
        \frac{1}{m}
        \sum \limits _{0 \leq j \lt m}
            \left(
                q_{i+j-1}-\mu_{Q_{i-1,m}}
            \right)
            \left(
                t_{i+j-1}-M_{T_{i-1,m}}
            \right)
    \\
    ={}&
        \frac{
            S(Q_{i,m-1},T_{i,m-1})
            +
            \frac{m-1}{m}
            \left(
                q_{i-1} 
                - 
                \mu_{Q_{i,m-1}} 
            \right)
            \left(
                t_{i-1}
                -
                M_{T_{i,m-1}} 
            \right)
        }{m}
    \\
    ={}&
        \frac{
            \frac{m-1}{m-1}S(Q_{i,m-1},T_{i,m-1})
            +
            \frac{m-1}{m}
            \left(
                q_{i-1} 
                - 
                \mu_{Q_{i,m-1}} 
            \right)
            \left(
                t_{i-1}
                -
                M_{T_{i,m-1}} 
            \right)
        }{m}
    \\
    ={}&
        \frac{
            cov(Q_{i,m-1},T_{i,m-1}) (m-1)
            +
            \left(
                \frac{m-1}{m}
            \right)        
            \left(
                q_{i-1} 
                - 
                \mu_{Q_{i,m-1}} 
            \right)
            \left(
                t_{i-1}
                -
                M_{T_{i,m-1}} 
            \right)
        }{m}
    \\
    ={}&
        \frac{m-1}{m} 
        \left[
            cov(Q_{i,m-1},T_{i,m-1})
            +
            \frac{
                \left(
                    q_{i-1} 
                    - 
                    \mu_{Q_{i,m-1}} 
                \right)
                \left(
                    t_{i-1}
                    -
                    M_{T_{i,m-1}} 
                \right)
            }{m}
        \right]
    \\
\end{align}

Now, we can rearrange write this and write represent $cov(Q_{i,m-1},T_{i,m-1})$ as a function of $cov(Q_{i-1,m},T_{i-1,m})$:

\begin{align}
    cov(Q_{i-1,m},T_{i-1,m})
    ={}&
        \frac{m-1}{m} 
        \left[
            cov(Q_{i,m-1},T_{i,m-1})
            +
            \frac{
                \left(
                    q_{i-1} 
                    - 
                    \mu_{Q_{i,m-1}} 
                \right)
                \left(
                    t_{i-1}
                    -
                    M_{T_{i,m-1}} 
                \right)
            }{m}
        \right]
    \\
    \frac{m}{m-1} 
    cov(Q_{i-1,m},T_{i-1,m})
    -
    \frac{
        \left(
            q_{i-1} 
            - 
            \mu_{Q_{i,m-1}} 
        \right)
        \left(
            t_{i-1}
            -
            M_{T_{i,m-1}} 
        \right)
    }{m}
    ={}&
        cov(Q_{i,m-1},T_{i,m-1})
    \\
\end{align}

And we can then substitute this representation of $cov(Q_{i,m-1},T_{i,m-1})$ into our $cov(Q_{i,m},T_{i,m})$ equation from above and get:

\begin{align}
    cov(Q_{i,m},T_{i,m})
    ={}&
        \frac{m-1}{m} 
        \left[
            cov(Q_{i,m-1},T_{i,m-1})
            +
            \frac{
                \left(
                    q_{i+m-1} - \mu_{Q_{i,m-1}}
                \right)
                \left(
                    t_{i+m-1} - M_{T_{i,m-1}}
                \right)
            }{m}
        \right]
    \\
    ={}&
        \frac{m-1}{m} 
        \left[
            \frac{m}{m-1}
            cov(Q_{i-1,m},T_{i-1,m})
            -
            \frac{
                \left(
                    q_{i-1} 
                    - 
                    \mu_{Q_{i,m-1}} 
                \right)
                \left(
                    t_{i-1}
                    -
                    M_{T_{i,m-1}} 
                \right)
            }{m}
            +
            \frac{
                \left(
                    q_{i+m-1} - \mu_{Q_{i,m-1}}
                \right)
                \left(
                    t_{i+m-1} - M_{T_{i,m-1}}
                \right)
            }{m}
        \right]
    \\
    ={}&
        cov(Q_{i-1,m},T_{i-1,m})
        +
        \frac{m-1}{m^2}
        \left[
            \left(
                q_{i+m-1} - \mu_{Q_{i,m-1}}
            \right)
            \left(
                t_{i+m-1} - M_{T_{i,m-1}}
            \right)
            -
            \left(
                q_{i-1} 
                - 
                \mu_{Q_{i,m-1}} 
            \right)
            \left(
                t_{i-1}
                -
                M_{T_{i,m-1}} 
            \right)
        \right]
    \\
\end{align}

# Pearson Correlation

\begin{align}
    \rho(Q_{i,m},T_{i,m}) 
    &{}= 
        \frac{cov(Q_{i,m},T_{i,m})}{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
    \\
    &{}=
        \frac{
            cov(Q_{i-1,m},T_{i-1,m})
        +
        \frac{m-1}{m^2}
        \left[
            \left(
                q_{i+m-1} - \mu_{Q_{i,m-1}}
            \right)
            \left(
                t_{i+m-1} - M_{T_{i,m-1}}
            \right)
            -
            \left(
                q_{i-1} 
                - 
                \mu_{Q_{i,m-1}} 
            \right)
            \left(
                t_{i-1}
                -
                M_{T_{i,m-1}} 
            \right)
        \right]
        }{\sigma_{Q_{i,m}}\Sigma_{T_{i,m}}}
    \\
\end{align}

# Z-Normalized Distance


```python

```

00ac95e310771e337d0487ccc9aa7c3242cddf73
ipynb
Jupyter Notebook
docs/Matrix_Profile_Derivation.ipynb
profintegra/stumpy
66b3402d91820005b466e1da6fe353b61e6246c5
BSD-3-Clause
2019-05-03T19:26:39.000Z
2022-03-31T20:42:08.000Z
docs/Matrix_Profile_Derivation.ipynb
vishalbelsare/stumpy
5f192a0a41fbb44f144cc4b676d525f19aaeaa98
BSD-3-Clause
2019-05-06T14:14:01.000Z
2022-03-31T20:39:31.000Z
docs/Matrix_Profile_Derivation.ipynb
vishalbelsare/stumpy
5f192a0a41fbb44f144cc4b676d525f19aaeaa98
BSD-3-Clause
2019-05-04T01:36:05.000Z
2022-03-31T20:31:11.000Z
Qwen/Qwen-72B
1. YES
2. YES