# A Novel Rolling Bearing Fault Diagnosis and Severity Analysis Method
## 2 Fast Sample Entropy  
### Principle of Sample Entropy  
The sample entropy is a measure of time series complexity proposed on the basis of the approximate entropy (ApEn) by [PERSON] in 2000 [30] and has been widely used in signal analysis.  
The time series \(\mathbf{X}(i)\) is denoted by \((\mathbf{X}_{i})_{m}\), which is convenient to illustrate the orthogonal range search. The implementation process is outlined below:  
For each element \(i(i=1,2,\ldots,N)\) in the time series, \((\mathbf{X}_{i})_{m}\) can be converted to the \(m\)-dimensional point set \(\mathbf{P}_{i}(\mathbf{x}_{i},\mathbf{y}_{i},\mathbf{z}_{i},\ldots)\),  
\[\mathbf{x}_{i}=\mathbf{X}_{i},\mathbf{y}_{i}=\mathbf{X}_{i+1},\mathbf{z}_{i}=\mathbf{X}_{i+2},\ldots. \tag{8}\]  
Then, \(\Theta(r-d[\mathbf{X}(i),\mathbf{X}(j)])\) is equal to the number of points contained within the bounding box \(W_{i}\), which can be expressed as  
\[W_{i}=\left[(x_{LB})_{i}:(x_{UB})_{i}\right]\times\left[(y_{LB})_{i}:(y_{UB}) _{i}\right]\times\left[(z_{LB})_{i}:(z_{UB})_{i}\right]\times\cdots, \tag{9}\]  
in which \(LB\) and \(UB\), respectively, represent the lower and upper bounds of the bounding box \(W_{i}\).  
\[\begin{array}{l}(x_{LB})_{i}=x_{i}-r,(x_{UB})_{i}=x_{i}+r\\ (y_{LB})_{i}=y_{i}-r,(y_{UB})_{i}=y_{i}+r\\ (z_{LB})_{i}=z_{i}-r,(z_{UB})_{i}=z_{i}+r\end{array} \tag{10}\]  
The number of points inside each bounding box queried by an orthogonal range in a \(d\)-dimensional space is called an orthogonal range search problem in computational geometry. Therefore, the calculation process of \(n_{i}^{m}\) is equivalent to an \(m\)-dimensional orthogonal range search for each point \(P_{i}\) and the corresponding boundary box \(W_{i}\). Once \(n_{i}^{m}\) and \(n_{i}^{m+1}\) are calculated, \(SampEn(m,r,N)\) can be obtained by Equation (7) directly and the time computing complexity depends on \(n_{i}^{m+1}\).  
The k-dimensional tree (kd tree) is a high-dimensional index tree data structure that is always used for the nearest neighbor domain search or approximate nearest neighbor domain search in large-scale high-dimensional data spaces. The kd tree can be used to resolve orthogonal range search problems to improve the computational efficiency of the SampEn [33]. The basic principle of the SampEn calculation based on the kd tree is to store the point set \(\mathbf{P}\) in the kd tree structure, which has a faster query speed for the points inside the specified boundary box.  
The main calculation process of the fast sample entropy based on the kd tree is summarized as follows:  
1. Coarse granulation of the time series \(\mathbf{X}\) is carried out. When the maximum time scale is 1, it means that time series \(\mathbf{X}\) has not been coarsely granulated;
2. The time series is transformed into the discrete space point set \(\mathbf{P}_{i}\), as shown in Equation (8);
3. Set \(k=m-1\) and build the kd tree structure by using the discrete space point set \(\mathbf{P}_{i}\);
4. For each discrete space point, obtain the bounding box \(W_{i}\) through Equation (9);
5. Obtain the number of discrete space points within bounding box \(W_{i}\) through the kd tree algorithm;
6. Set \(k=m\) and repeat steps (2) to (5), calculating \(n_{d}(i)\);
7. Utilize \(n_{n}(i)\) and \(n_{d}(i)\) to calculate \(SampEn(m,r,N)\).  
The time computing complexity of the above kd tree-based sample entropy calculation method is mainly composed of the spatial point transformation process, the kd tree establishment process, and the query process. According to the literature [34], the time computing complexity of the whole SampEn calculating process based on the kd tree is \(O(N\bullet N^{1-(1/d)})\). When \(m=2\), the time computing complexity of the SampEn calculation method based on the kd tree is reduced to \(O(N^{5/3})\).