DTW

Dynamic Time Warping (DTW) is a similarity measure for temporal sequences that may vary in speed. It aligns two sequences by warping their time axes to minimize differences between corresponding elements. DTW has been widely applied in speech recognition, handwriting analysis, gesture recognition, and other time-series domains. Given two sequences X = (x1, ..., xn) and Y = (y1, ..., ym), DTW seeks an optimal alignment path that minimizes the cumulative distance between paired points after time warping.

To define DTW, specify a local distance d(x_i, y_j) (commonly the Euclidean distance). A warping path P is a sequence of index pairs (i_k, j_k) starting at (1,1) and ending at (n,m), with non-decreasing indices and steps restricted to (1,0), (0,1), or (1,1). The DTW distance is the minimum over P of the sum of d(x_i, y_j) along the path. This minimum is computed by dynamic programming with D[i,j] = d(x_i, y_j) + min(D[i-1,j], D[i,j-1], D[i-1,j-1]), and D[1,1] = d(x1,y1). The final distance is D[n,m], and the optimal path can be recovered by backtracking. Complexity is O(nm).

Variants and enhancements include constraining the warping window (e.g., Sakoe-Chiba band, Itakura parallelogram) to improve efficiency and robustness, and derivative DTW (DTW-D) or soft-DTW, which provides differentiable objectives for machine learning. Extensions to multi-dimensional time series and efficient parallel implementations are common.

DTW is widely used for comparing time series with speed variations but has limitations: it can over-align noisy sequences, requires normalization of amplitudes, and is computationally intensive for long series. It is not a metric in general, since the triangle inequality may fail. Nevertheless, DTW remains a foundational tool in time-series analysis and pattern recognition.