Key result
The proposed Monte Carlo-based algorithm for estimating sample entropy achieved a 100-1000 times speedup compared to kd-tree and assisted sliding box algorithms while providing satisfactory accuracy.
Why the study?
Existing algorithms to compute sample entropy in time series have high computational complexity, leading to large computational costs when the time series length is big.
Effect estimate: 100-1000 times speedup
A novel Monte Carlo-based algorithm significantly accelerates the computation of sample entropy for physiological and other time series data by 100-1000 times.
May enable real-time sample entropy use in cardiac monitoring; leaves open prospective validation in clinical datasets.
Sample entropy, an approximation of the Kolmogorov entropy, was proposed to characterize complexity of a time series, which is essentially defined as −log(B/A), where B denotes the number of matched template pairs with length m and A denotes the number of matched template pairs with m+1, for a predetermined positive integer m. It has been widely used to analyze physiological signals. As computing sample entropy is time consuming, the box-assisted, bucket-assisted, x-sort, assisted sliding box, and kd-tree-based algorithms were proposed to accelerate its computation. These algorithms require O(N2) or O(N2−1m+1) computational complexity, where N is the length of the time series analyzed. When N is big, the computational costs of these algorithms are large. We propose a super fast algorithm to estimate sample entropy based on Monte Carlo, with computational costs independent of N (the length of the time series) and the estimation converging to the exact sample entropy as the number of repeating experiments becomes large. The convergence rate of the algorithm is also established. Numerical experiments are performed for electrocardiogram time series, electroencephalogram time series, cardiac inter-beat time series, mechanical vibration signals (MVS), meteorological data (MD), and 1/f noise. Numerical results show that the proposed algorithm can gain 100–1000 times speedup compared to the kd-tree and assisted sliding box algorithms while providing satisfactory approximate accuracy.
No takes yet. Share an insight, caveat, or question.
Liu et al. (2022) studied this question. Monte Carlo-based super fast algorithm for estimating sample entropy vs. kd-tree and assisted sliding box algorithms was evaluated on Computational speedup and approximate accuracy (100-1000 times speedup). The proposed Monte Carlo-based algorithm for estimating sample entropy achieved a 100-1000 times speedup compared to kd-tree and assisted sliding box algorithms while providing satisfactory accuracy.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: