Dynamic Time Warping

Question

The dynamic time warping algorithm provides a notion of distance between two trajectories $s$ and $t$ with points indexed by $s_i$ and $t_j$. The dynamic programming algorithm is only a few lines and the key formula is:

$$D(i+1,j+1)=cost+min\{D(i,j+1),D(i+1,j),D(i,j)\},$$ where $$cost=norm(s_i-t_j).$$

After looping for $i$ and $j$ the last element of the cache matrix $d=D(size(s)+1,size(t)+1)$ provides the dynamic time warping distance. This value should correspond to the optimal trajectory alignment in the sense that the sum of euclidean pairwise distances is minimized. Moreover, valid trajectory alignments should satisfy some simple rules such as monotonicity.

I am not able to see why such a recursive algorithm provides the solution to this minimization problem. Is it trivial? Can someone help me understand this?

Answer 1

Fix index $(i+1, j+1)$. There is a few decisions you can choose:

• Connect $s_{i+1}$ to $t_{j+1}$ only (Meaning each of them are only connected to each other). This would cost you $||s_i-t_j||$, plus the cost of connecting $s_1, .., s_i$ to $t_1, .., t_j$, or $D(i,j)$.
• Connect $s_{i+1}$ to $t_{j+1}$, but allow $s_{i+1}$ to be connected to more than one, and $t_{j+1}$ to be connected to only one (which is $s_{i+1}$). This is $D(i+1, j)+||s_i-t_j||$
• Connect $s_{i+1}$ to $t_{j+1}$, but allow $t_{j+1}$ to be connected to more than one, and $s_{i+1}$ to be connected to only one (which is $t_{j+1}$). This is $D(i, j+1)+||s_i-t_j||$

We want the decision that minimizes the time warping distance. So we take the minimum of all of them, and you get your recurrence.