N-Step Sliding Recursion Formula of Variance and Its Implementation


Lang Yu, Gang He, Ahmad Khwaja Mutahir, Journal of Information Processing Systems Vol. 16, No. 4, pp. 832-844, Aug. 2020  

https://doi.org/10.3745/JIPS.04.0182
Keywords: Algorithm Complexity, Multi-Step Recursion Algorithm, sliding window, Variance
Fulltext:

Abstract

The degree of dispersion of a random variable can be described by the variance, which reflects the distance of the random variable from its mean. However, the time complexity of the traditional variance calculation algorithm is O(n), which results from full calculation of all samples. When the number of samples increases or on the occasion of high speed signal processing, algorithms with O(n) time complexity will cost huge amount of time and that may results in performance degradation of the whole system. A novel multi-step recursive algorithm for variance calculation of the time-varying data series with O(1) time complexity (constant time) is proposed in this paper. Numerical simulation and experiments of the algorithm is presented and the results demonstrate that the proposed multi-step recursive algorithm can effectively decrease computing time and hence significantly improve the variance calculation efficiency for time-varying data, which demonstrates the potential value for time-consumption data analysis or high speed signal processing.


Statistics
Show / Hide Statistics

Statistics (Past 3 Years)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.




Cite this article
[APA Style]
Yu, L., He, G., & Mutahir, A. (2020). N-Step Sliding Recursion Formula of Variance and Its Implementation. Journal of Information Processing Systems, 16(4), 832-844. DOI: 10.3745/JIPS.04.0182.

[IEEE Style]
L. Yu, G. He, A. K. Mutahir, "N-Step Sliding Recursion Formula of Variance and Its Implementation," Journal of Information Processing Systems, vol. 16, no. 4, pp. 832-844, 2020. DOI: 10.3745/JIPS.04.0182.

[ACM Style]
Lang Yu, Gang He, and Ahmad Khwaja Mutahir. 2020. N-Step Sliding Recursion Formula of Variance and Its Implementation. Journal of Information Processing Systems, 16, 4, (2020), 832-844. DOI: 10.3745/JIPS.04.0182.