The Multiscale Entropy Algorithm and Its Variants: A Review <s> Computational Efficiency <s> Recently, the utility of sample entropy (SampEn) as a complexity measure was shown via applying to time series data generated from in a variety of systems. However, online estimation method of SampEn index has not been developed yet. If SampEn can be estimated online, we can apply this index to time-varying system. In this paper, we developed the recursive SampEn algorithm to estimate the changes of system complexity online. In addition, we verified the utility of this algorithm by simulations. Consequently, we assure that this algorithm can be applied to time series generated from in a variety of time-varying system potentially. <s> BIB001 </s> The Multiscale Entropy Algorithm and Its Variants: A Review <s> Computational Efficiency <s> Sample entropy (SaEn) was recently developed to quantify the amount of regularity in data. However, the computation of this feature in an online application is infeasible. In this work, we examine a heuristic approach using permuted limited number of samples to estimate SaEn and discuss estimation variability in this context. We conclude that the computation of permuted SaEn provides a fair estimate of time series regularity that can be used in online applications. <s> BIB002 </s> The Multiscale Entropy Algorithm and Its Variants: A Review <s> Computational Efficiency <s> Multi-scale entropy (MSE) is a measurement of a system's complexity. It has received a great deal of attention in recent years, and its effectiveness has been verified, and applied in a number of different fields. However, the algorithms proposed in past studies required O (N^2), which represented a degree of execution time insufficient for on-line applications, or for applications with long term correlations. In this study, we showed that the probability function in the entropy term could be transformed into an orthogonal range search in the field of computational geometry. We then developed an efficient new algorithm for computing multi-scale entropy. The execution time in the results of our experiments with electrocardiogram (ECG), electroencephalography (EEG), interbeat interval (RR), and mechanical and ecological signals showed a significant improvement from 10 to 70 times over that of conventional methods for N=80, 000. Because the execution time has been significant reduced, the new algorithm could be applied to online diagnosis, in the computation of MSE for long-term correlation of signal. <s> BIB003 </s> The Multiscale Entropy Algorithm and Its Variants: A Review <s> Computational Efficiency <s> Sample entropy is a widely used tool for quantifying complexity of a biological system. Computing sample entropy directly using its definition requires large computational costs. We propose a fast algorithm based on a k-d tree data structure for computing sample entropy. We prove that the time complexity of the proposed algorithm is $O(N^{2-\frac{1}{m+1}})$ and its space complexity is O(N log N), where N is the length of the input time series and m is the length of its pattern templates. We present a numerical experiment that demonstrates significant improvement of the proposed algorithm in computing time. <s> BIB004
The computational time of the original MSE algorithm prevents online applications or even the processing of long data sets (the time complexity of the algorithm is O(N 2 )). This is due to the computational time of the sample entropy value. In order to overcome this drawback, Sugisaki et al. developed, in 2007, a recursive sample entropy algorithm for the situation when rolling windows overlapped, in order to be able to use the complexity measure (sample entropy algorithm) online BIB001 . Their algorithm uses a variable forgetting factor mechanism. However, the algorithm proposed by Sugisaki et al. has two drawbacks BIB003 : the computed sample entropy is an approximation, and the computational efficiency decays with a decrease in overlap length (the improvement does not exist when overlap length is zero). Samani and Madeleine proposed another algorithm to compute sample entropy for online applications BIB002 . Their algorithm uses permuted limited number of samples to estimate sample entropy. Later, Pan et al. went further BIB003 . They showed that the probability function in entropy could be transformed into an orthogonal range search problem in the field of computational geometry BIB003 . The algorithm that they proposed for the computation of MSE is based on a k-d tree algorithm. The authors reported that their algorithm reduces the computational time and mentioned that this new algorithm can be used for online applications BIB003 . In 2011, Jiang et al. also proposed an algorithm to compute sample entropy with less computational time. As for Pan et al., their algorithm relies on a k-d tree data structure to accelerate counting the number of matched pairs of the pattern templates BIB004 . The authors reported that the time complexity of their algorithm is O(N 2− 1 m+1 ) and its space complexity is O (N log 2 N ) , where N is the time series length and m is the length of the pattern templates.