How to create a pairwise DTW cost matrix?

Question

I am trying to create a pairwise DTW (Dynamic Time Warping) matrix in python. I have the below code already, but it is incorrect somehow. My current output is a matrix full of infinity, which is incorrect. I cannot figure out what I am doing incorrectly.

def calc_pairwise_dtw_cost(x, y):
    
    cost_matrix = np.zeros((len(y), len(x)))
    dtw_cost = None


    for i in range(0, len(y)):
        for j in range(0, len(x)):
            cost_matrix[i, j] = float('inf')
        

    for i in range(1, len(y)):
        for j in range(1, len(x)):
            dtw_cost = cost_matrix[-1,-1]
            cost_matrix[i, j] = dtw_cost + min(
                cost_matrix[i-1, j],    # insertion
                cost_matrix[i, j-1],    # deletion
                cost_matrix[i-1, j-1])   # match

    return cost_matrix

Current output is:

array([[inf, inf, inf, ..., inf, inf, inf],
       [inf, inf, inf, ..., inf, inf, inf],
       [inf, inf, inf, ..., inf, inf, inf],
       ...,
       [inf, inf, inf, ..., inf, inf, inf],
       [inf, inf, inf, ..., inf, inf, inf],
       [inf, inf, inf, ..., inf, inf, inf]])

Answer 1

In your implementation there are several errors including:

• neglecting to make use of inputs arrays x, y
• cost_matrix is not declared with the right dimensions
• cost_matrix[0,0] should be initialize to 0

Dynamic Time Warping: Explanation and Code Implementation provides an implementation of DTW that follows the Wikipedia pseudo-code closely as follows.

Code

def dtw(s, t):
    n, m = len(s), len(t)
    dtw_matrix = np.zeros((n+1, m+1))  # note the +1 added to n & m
    for i in range(n+1):
        for j in range(m+1):
            dtw_matrix[i, j] = np.inf
    dtw_matrix[0, 0] = 0               # [0,0] element set to 0
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            cost = abs(s[i-1] - t[j-1]) # use inputs s & t
            # take last min from a square box
            last_min = np.min([dtw_matrix[i-1, j], dtw_matrix[i, j-1], dtw_matrix[i-1, j-1]])
            dtw_matrix[i, j] = cost + last_min
    return dtw_matrix

Answer 2

Under IEEE 754 rules, inf + anything is inf. Since you filled your matrix with infinities, then read a value out of it and added another, you can't help but get an infinite result.