Physica A 400 (2014) 159–167
Contents lists available at ScienceDirect
Physica A
journal homepage: www.elsevier.com/locate/physa
On the computational complexity of the empirical mode
decomposition algorithm
Yung-Hung Wang
a
, Chien-Hung Yeh
a,b
, Hsu-Wen Vincent Young
a
, Kun Hu
c
,
Men-Tzung Lo
a,∗
a
Research Center for Adaptive Data Analysis, National Central University, Chungli, Taiwan, ROC
b
Department of Electrical Engineering, National Central University, Chungli, Taiwan, ROC
c
Medical Biodynamics Program, Division of Sleep Medicine, Brigham and Women’s Hospital, Harvard Medical School,
Boston, MA 02115, United States
h i g h l i g h t s
• The order of the computational complexity of the EMD is equivalent to FFT.
• Optimized program is proposed to speed up the computation of EMD up to 1000 times.
• Fast HHT with optimized EMD/EEMD algorithm can operate in real-time.
a r t i c l e i n f o
Article history:
Received 30 October 2013
Received in revised form 30 December 2013
Available online 21 January 2014
Keywords:
EMD
EEMD
Time
Space
Complexity
a b s t r a c t
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.
© 2014 Elsevier B.V. All rights reserved.
1. Introduction
EMD [1] is a nonlinear and nonstationary time domain decomposition method. It is an adaptive, data-driven algorithm
that decomposes a time series into multiple empirical modes, known as intrinsic mode functions (IMFs). Each IMF
represents a narrow band frequency–amplitude modulation that is often related to a specific physical process. For signals
with intermittent oscillations, one intrinsic mode can comprise oscillations with a variety of wavelengths at different
temporal locations. Collectively, the simultaneous exhibition of these disparate oscillations is known as the mode mixing
phenomenon, which can complicate analyses and obscure physical meanings. To overcome this problem, the EEMD
algorithm [2] and the noise-assisted MEMD [3] have been proposed. In particular, the EEMD has drawn a lot of attention
Abbreviations: EMD, empirical mode decomposition; EEMD, ensemble empirical mode decomposition; IMFs, intrinsic mode functions; MEMD,
multivariate empirical mode decomposition; ADD, addition; MUL, multiplication; DIV, division; COMP, comparison; BFV, blood flow velocity signal.
∗
Correspondence to: Research Center for Adaptive Data Analysis/National Central University, No. 300, Jhongda Rd., Jhongli City, Taoyuan County 32001,
Taiwan, ROC. Tel.: +886 3 426 9734; fax: +886 3 426 9736.
0378-4371/$ – see front matter © 2014 Elsevier B.V. All rights reserved.
http://dx.doi.org/10.1016/j.physa.2014.01.020
评论0