# Computational burden of EMD/Huang-Hilbert vs wavelet

I am working on an online application of signal processing and pattern recognition. It involves sampling the signal at 2 MS/s, extracting features and classifying.

My classifier has pretty good accuracy so far using the DWT (discrete wavelet transform) with 3 decomposition levels. However, I have been studying the EMD (Empirical Mode Decomposition) and trying to apply it to the problem since my data is highly non-stationary. The algorithms that I got are waaaaaay slower than the wavelet and PSD (power spectral density) estimation by Welch's method (another one that I was using.)

Is this normal/expected behavior? For wideband data is possible to implement it to work online?

Sorry about the broad question, it seems that it is more a curiosity for discussion that anything.

There are relationships between fixed wavelets and EMD, for certain classes of signals, cf. Empirical Mode Decompositions as data-driven wavelet-like wavelet-like expansions. A related relation between a fixed basis and an adaptive one can be found between Fourier transforms and Karhunen-Loève/PCA type decompositions.

Of course, when the vectors used for representations are learnt instead of being fixed beforehand, they are likely to require more computations. And are likely to be more difficult to implement online. Plus, DWT are often critically sampled, while EMD are redundant (hence greedier). Yet, some papers (see below) evaluate it proportionally to the burden of the FFT. Roughly to that of a redundant stationary wavelet transform.

Then, for non constrained versions, EMD can be quite sensitive to border effect, local spike instability, etc. As a result, from one signal to a similar other, a different number of IMFs can be necessary, which is not the case of a fixed-level DWT (but you can find that with adaptive wavelet packets).

Further, each can be sensitive to the features you can extract.

So yes, it is not so surprising to me, with experience on seismic data and combustion signals with sporadic instabilities. Yet, it can work on some data.

Finally, some online implementations exist:

On-chip implementation of Hilbert-Huang transform (HHT) has great impact to analyze the non-linear and non-stationary biomedical signals on wearable or implantable sensors for the real-time applications. Empirical mode decomposition (EMD) is the key component for the HHT processor. In tradition, EMD is usually performed after the collection of a large window of signals, and the long latency may not be feasible for the real-time applications. In this work, the architecture of on-line EMD for biomedical signals is proposed. The on-line interpolation method with data reuse as well as component and iteration loop decomposition is applied to obtain low latency and low hardware cost. The first chip of EMD processor is fabricated in UMC 90nm LL process and consumes 57.3µW.

The success of Empirical Mode Decomposition (EMD) resides in its practical approach to dissect non-stationary data. EMD repetitively goes through the entire data span to iteratively extract Intrinsic Mode Functions (IMFs). This approach, however, is not suitable for data stream as the entire data set has to be reconsidered every time a new point is added. To overcome this, we propose Online EMD, an algorithm that extracts IMFs on the fly. The two key elements of Online EMD are a sliding window to compute local IMFs, and a stitching procedure to gradually append local IMFs to the final result. Using synthetic data we show that the decomposition quality of Online EMD is similar to classical EMD. We also present results obtained with a real data set to expose the practical advantages of Online EMD when dealing with data stream or large data set.

It has been claimed that the empirical mode decomposition (EMD) and its improved version the ensemble EMD (EEMD) are computation intensive. In this study we will prove that the time complexity of the EMD/EEMD, which has never been analyzed before, is actually equivalent to that of the Fourier Transform. Numerical examples are presented to verify that EMD/EEMD is, in fact, a computationally efficient method.

• Wow.. thanks a lot. I think I will need time to digest all this, but as a 'take home' for others, it seems that I am limited by the size of my data. Large windows require many iterations when extracting the IMFs and this can be time-consuming. In my case, I still have to consider interpolation or smaller windows but I think it can generate loss of information as the quick transients are of much importance. Anyway, I will keep it posted in case of any news. Thanks again. Commented Nov 9, 2017 at 3:12
• Do you happen to remember the name of the papers? I am so dumb that I had to open MATLAB to see which one is bigger. Commented Nov 9, 2017 at 7:52
• Done. I think this should be taken with caution: for 2 signals of the same length, the complexity of a DWT will be the same. While the number of iterations for EMD may be different (up to the tolerance) Commented Nov 9, 2017 at 12:15