How to get DTW to run faster?

Question

I have a matrix with 4500 vectors of 1800 length, for which I need to compute the DTW (Dynamic Time Warping) distance between every 2 vectors in the matrix.

I have used a nested loop to fill up half of a 4500x4500 matrix (which would look like a triangle):

matr = zeros(4500,4500); %initializing empty matrix to fill dtw distance
for i=1:4500
    x = new(i,:); %new is where the data lies
    for j = i+1:4500
        y = new(j,:);
        matr(i,j) = dtw(x,y);
    end
end

The problem is that the code runs extremely slow. And as per my calculation it will take 4 days to run on my computer.

I have no clue of how vectorization works. But is there a way my code can be vectorized so that it runs faster? Also isn't there an inbuilt function where I could just plug in all my vectors and get a DTW dist matrix auto generated?

Answer 1

No, there is no obvious way to vectorize your code in Matlab to make it faster. You are asking for a lot of computation (~4500^2 / 2 DTW calculations) and it will probably take time no matter what you do. But you have some options:

• If you only need to do this computation once, just run it and wait four days. If you are at a school or company, you may be able to run it on a computer other than your personal one.
• You can try using dtw inside a call to pdist2 as a custom distance function. This may be slightly faster.
• You can write your own DTW in Matlab and try to save time there. One obvious speedup is that each call to dtw must allocate a 1800x1800 matrix. In your own code, you could allocate this once and reuse it.
• You can write your own DTW in another language, or use someone else's DTW code from another language. These could be called from Matlab via MEX and might be faster depending on the language and implementation.
• You could settle for an approximation. For example, pick a reference signal, x0, and compute dtw(x0, xi) for each of your 4500 vectors. Then make the approximation that dtw(xi, xj) = dtw(x0, xi) + dtw(x0, xj). Doing this is about 4500 times faster than what you propose.