On the Computational Complexity of Sample Entropy and Its Edge Computing

Sample entropy (SpEn) is a measure of underlying regularity or complexity of a system, which has received increasing attention in recent years and has been successfully applied in biomedical applications and others. However the standard implementation of SpEn requires computational complexity of O(n^2) (n is the data length), and is rather time consuming when applying to a long data set and imposes difficulties in real-time applications in embedded system. The computation of sample entropy is, in fact, is an orthogonal range search problem in the field of computational geometry in computer science. To be more specific, it is equivalent to count the total neighbors in m- (and m—1) dimensional embedded phase space. Because most of the biological signal is stored in finite resolution (R) format, it allows us to develop fast algorithm. In addition, the method can be applied to real signal after slightly modification. The goals of this proposal are:We will propose an adaptive 2^m-tree algorithm (AM-tree). The computational complexity of this algorithm is faster than any of algorithms in the literature. Let R being the resolution of the signal. We will prove that the method is with O(kn) linear computational complexity and linear memory. The parameter k is function of log_2Rand m.We will execute the developed algorithms in a micro-controller (MCU) for real-time illness detection and health monitoring. The algorithm will speed up the execution time by a factor of 100 and save 99% power consumption. We will use a whole night brain wave and HRV signals as examples to demonstrate the efficacy of the proposed algorithm