A faster findsignal method

Question

Matt Flax 2021-10-17

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565366-a-faster-findsignal-method

评论： Matt Flax 2021-10-20

findsignal implements a method for finding the best similairty between two signals. findsignal is slow.

Is there a faster way to execute findsignal ?

2 个评论
显示无隐藏无

Eamonn 2021-10-20

You are in luck!

The MASS algorithm is much faster, and is more general

https://www.cs.unm.edu/~mueen/FastestSimilaritySearch.html

MASS supports GPUs

If you want to see case studies etc, Google "100 Time Series Data Mining Questions (with Answers!)"

Matt Flax 2021-10-20

Nice site! The DFT method is good for longer signals.For shorter signals this is more efficient : https://au.mathworks.com/matlabcentral/fileexchange/100893-findsimilarity

I also tested your code sing gpuArray, however that significantly slows down the computation for shorter signals as well !

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2021-10-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565366-a-faster-findsignal-method#answer_810131

Maybe. It would not astonish me if parts if it could be rewritten to use an available GPU.

However... the algorithm already invokes two mex functions to improve performance, so you might be hard-pressed to find a more efficient algorithm.

The algorithm involves normalization of signals, and involves calculating dynamic time warping (dtw) https://www.mathworks.com/help/signal/ref/dtw.html to try to find the best match. The dtw is one of the portions done as mex.

You might be able to find a different algorithm, but you would need to ask whether it is doing the same job as findsignal() is doing. For example, some people might be satisfied with xcorr() https://www.mathworks.com/help/matlab/ref/xcorr.html but that does not have the same behaviour of trying to find the best possible place for the signals to fit together including stretching.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Matt Flax 2021-10-17

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/1565366-a-faster-findsignal-method#answer_810151

在 MATLAB Online 中打开

I see, thanks for the information. Yes, xcorr will not work because it has no form of error or difference measure.

The core algorithm of interest is (the same as findsignal.m) the algorithm used in Waveform Similarity Overlap Add (WSOLA), specifically the algorithm for similarity searching : https://github.com/flatmax/gtkiostream/blob/master/src/WSOLA.C#L62

Which can be written in Matlab like so to find a similar signal to s in the vector y :

Ns=size(s,1);
res=buffer(y,Ns,Ns-1,'nodelay');
res=s-res;
errM=rms(res);
[err,nI]=min(errM);

It is interesting that when profiling the above non-mex code, it is similar in speed to the findsignal.m algorithm. The buffer code is heavy on memory allocation which is slow. The rms method is not a mex code.

It would seem that there is possibly scope to improve the speed somewhere ?

Matt