In DTW, is the distance the sum of the shortest path's elements or the fathest element?

Question

The title says it. In dynamic time warping, I keep hearing that the distance between two distances is the sum of the shortest path's elements. But I also see the distance as the element in the farthest corner? Could somebody please clear this up.

Example:

x = [0,1,1,2]
z = [0,2,2]

gives this cost matrix:

[[ 0. inf inf inf]
 [inf  0.  2.  4.]
 [inf  1.  1.  2.]
 [inf  2.  2.  2.]
 [inf  4.  2.  2.]]

meaning that the distance should be 0 + 0 + 1 + 2 + 2 = 5. But every dtw implementation I found returns the distance is 2 (i.e. always returns element in the farthest corner). Thank you!

Answer 1

There's a confusion about how the algorithm works.

DTW is inspired by the Levenshtein edit distance, which is an example of dynamic programming to calculate the minimum distance efficiently. The main idea is to incrementally calculate the minimum distance between any two subsequences $1..i$ and $1..j$.

So the DTW matrix is not a cost matrix, at least not in the sense of cost between individual positions. any cell in the matrix $m[i,j]$ is the smallest possible distance between the subsequences $1..i$ and $1..j$, so that the last cell $m[m,n]$ already contains the smallest distance for the full sequences. In other words there's nothing to sum, actually summing the values doesn't make sense since the larger subsequences include the smaller ones.