Sifting process, which is recursive in nature, is used in EMD (Empirical Mode Decomposition) to decompose the signal (x(t)) into Intrinsic Mode Functions (IMFs) and residue, which is a monotonic function. All the examples provided of Sifting is recursive and all parallel implementation of EMDs where GPU or GPGPU or FPGA are utilized (Example), only use the parallel nature of hardware to speedup the mode decomposition algorithm rather than parallelizing the Siting process instead.

Is it possible to parallelize the Sifting process? If Yes, then do you happen to have any ideas regarding this?


Is it possible to parallelize the Sifting process?


The "problem" here is not the recursion itself but the fact that the data changes at each recursion step.

It is possible to parallelise divide and conquer type of algorithms that imply hierarchy as is the case of the split radix FFT or Quicksort for example. But in that case, the input sequence of values, let's call it $x[n]$ does not change with every step of recursion. Therefore, this ends up being an "exercise" in managing subsequences and the results of function application. Consequently, it is possible to resolve recursion by storing which indices are supposed to be processed at each step of recursion and storing them on a list, effectively transforming recursion to iteration.

Contrast this with empirical mode decomposition where the vector that is sent to the lower (or higher) levels of recursion is not $x[n]$ but $x[n]-q[n]$ where $q[n]$ is the mean waveform that is formed by combining the maxima and minima interpolated wavefoms.

In this way, the maxima and minima of the second level depend on the subtraction of the previous level. It is not simply a matter of finding the "first order" maxima and minima, then the "second order" maxima and minima, then the third order and so on and then recombining them at different levels of recursion because the first level subtraction has the potential to change which $x[n]$ become local maxima (or minima) at a subsequent step.

Therefore, empirical mode decomposition has an inherent sequential part that cannot be parallelised.

Hope this helps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.