Graphical time warping (GTW) is a framework for jointly aligning multiple pairs of time series or sequences. GTW considers both the alignment accuracy of each sequence pair and the similarity among pairs. On contrary, alignment with dynamic time warping (DTW) considers the pairs independently and minimizes only the distance between the two sequences in a given pair. Therefore, GTW generalizes DTW and could achieve a better alignment performance when similarity among pairs is expected. One application of GTW is signal propagation analysis in time-lapse bio-imaging data, where the propagation patterns in adjacent pixels are generally similar. Other applications include signature identification, binocular stereo depth calculation, and liquid chromatography–mass spectrometry (LC-MS) profile alignment in proteomics data analysis. Indeed, as long as the data are structured with inter-dependent time series/sequences, they can be analyzed with GTW. GTW is able to model constraints or similarities between warping paths by transforming the DTW-equivalent shortest path problem to the maximum flow problem in the dual graph, which can be solved by most max-flow algorithms. However, when the data is large, these algorithms become time-consuming and the memory usage is high. An efficient algorithm, Bidirectional pushing with Linear Component Operations (BILCO), was developed to solve the GTW problem. It could achieve an average 10-fold improvement in both computational and memory usage compared with the state of art generic maximum flow algorithms in GTW applications.
Joint alignment and GTW formulation
Joint alignment Assume there are N {\displaystyle N} pairs of time series { ( x n , y n ) | n = 1 , 2 , . . . , N } {\displaystyle \{(x_{n},y_{n})|n=1,2,...,N\}} , and each pair x n , y n {\displaystyle {x_{n},y_{n}}} has a corresponding warping path P n {\displaystyle P_{n}} . Some pairs of warping paths are known to be similar, and the set of all such pairs is denoted as ( m , n ) {\displaystyle {(m,n)}} . For example, if ( m , n ) {\displaystyle (m,n)} is in this set, warping paths P m {\displaystyle P_{m}} and P n {\displaystyle P_{n}} are similar. To optimize both the similarity between the aligned time series and the warping paths distances, the joint alignment problem is formulated as a minimization problem:
min { P n | n = 1 , 2 , . . . , N } ( ∑ n = 1 N c o s t ( P n ) + κ ∑ ( m , n ) ∈ N e i b d i s t ( P m , P n ) ) {\displaystyle \min _{\{P_{n}|n=1,2,...,N\}}\left(\sum _{n=1}^{N}cost(P_{n})+\kappa \sum _{(m,n)\in Neib}dist(P_{m},P_{n})\right)}
… excerpt ends here. Continue reading the full article.
