Fast Constrained Sparse Dynamic Time Warping

Dynamic Time Warping (DTW) has been proposed to solve machine learning problems when comparing time series. Such time series can occasionally be sparse due to the inclusion of zero-values at many epochs. Since the traditional DTW does not utilize the sparsity of time series data, various fast algorithms equivalent to DTW were developed: (1) Sparse Dynamic Warping (SDTW); (2) Constrained Sparse Dynamic Time Warping (CSDTW) with the constraint on the warping path; (3) Fast Sparse Dynamic Time Warping (FSDTW) as a fast approximate algorithm of SDTW. This paper develops and analyzes a fast algorithm that approximates CSDTW, Fast Constrained Sparse Dynamic Time Warping (FCSDTW). FCSDTW significantly decreases the computational complexity compared to constrained DTW (CDTW) and also shows speed improvement against CSDTW with negligible errors. This study should add to a framework in sparsity exploitation for reducing complexity.