On the Computational Complexity of Sample Entropy and Its Edge Computing

Project Details


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
Effective start/end date1/08/2031/07/21

UN Sustainable Development Goals

In 2015, UN member states agreed to 17 global Sustainable Development Goals (SDGs) to end poverty, protect the planet and ensure prosperity for all. This project contributes towards the following SDG(s):

  • SDG 3 - Good Health and Well-being
  • SDG 12 - Responsible Consumption and Production
  • SDG 17 - Partnerships for the Goals


  • sample entropy
  • computational complexity
  • edge computing
  • brain wave


Explore the research topics touched on by this project. These labels are generated based on the underlying awards/grants. Together they form a unique fingerprint.