Journal of Information Processing Systems

Korea Information Processing Society (한국정보처리학회)
권호 표지
DOI QR코드

DOI QR Code

N-Step Sliding Recursion Formula of Variance and Its Implementation

  • Yu, Lang (School of Science, Southwest University of Science and Technology) ;
  • He, Gang (School of Computer Science and Technology, Southwest University of Science and Technology) ;
  • Mutahir, Ahmad Khwaja (School of Computer Science and Technology, Southwest University of Science and Technology)
  • Received : 2019.03.08
  • Accepted : 2019.06.08
  • Published : 2020.08.31
Download PDF
⟨ Previous Next ⟩

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.

Keywords

References

  1. R. A. Fisher, "XV.-The correlation between relatives on the supposition of Mendelian inheritance," Earth and Environmental Science Transactions of the Royal Society of Edinburgh, vol. 52, no. 2, pp. 399-433, 1919. https://doi.org/10.1017/S0080456800012163
  2. S. Orcioni, S. Cecchi, and A. Carini, "Multivariance nonlinear system identification using wiener basis functions and perfect sequences," in Proceedings of 2017 25th European Signal Processing Conference (EUSIPCO), Kos, Greece, 2017, pp. 2679-2683.
  3. S. Baek and D. Y. Kim, "Abrupt variance and discernibility analyses of multi-sensor signals for fault pattern extraction," Computers & Industrial Engineering, vol. 128, pp. 999-1007, 2019. https://doi.org/10.1016/j.cie.2018.06.019
  4. S. Durant, I. Sulykos, and I. Czigler, "Automatic detection of orientation variance," Neuroscience Letters, vol. 658, pp. 43-47, 2017. https://doi.org/10.1016/j.neulet.2017.08.027
  5. J. Y. Gotoh, M. J. Kim, and A. E. Lim, "Robust empirical optimization is almost the same as mean-variance optimization," Operations Research Letters, vol. 46, no. 4, pp. 448-452, 2018. https://doi.org/10.1016/j.orl.2018.05.005
  6. N. Gatzert, "An analysis of transaction costs in participating life insurance under mean-variance preferences," Insurance: Mathematics and Economics, vol. 85, pp. 185-197, 2019. https://doi.org/10.1016/j.insmatheco.2019.01.003
  7. C. S. Pun, "Time-consistent mean-variance portfolio selection with only risky assets," Economic Modelling, vol. 75, pp. 281-292, 2018. https://doi.org/10.1016/j.econmod.2018.07.002
  8. M. Zhang and P. Chen, P"Mean-variance asset-liability management under constant elasticity of variance process," Insurance: Mathematics and Economics, vol. 70, pp. 11-18, 2016. https://doi.org/10.1016/j.insmatheco.2016.05.019
  9. T. Bodnar, N. Parolya, and W. Schmid, "Estimation of the global minimum variance portfolio in high dimensions," European Journal of Operational Research, vol. 266, no. 1, pp. 371-390, 2018. https://doi.org/10.1016/j.ejor.2017.09.028
  10. A. Clements and Y. Liao, "Forecasting the variance of stock index returns using jumps and cojumps," International Journal of Forecasting, vol. 33, no. 3, pp. 729-742, 2017. https://doi.org/10.1016/j.ijforecast.2017.01.005
  11. A. Kaeck, P. Rodrigues, and N. J. Seeger, "Equity index variance: evidence from flexible parametric jump-diffusion models," Journal of Banking & Finance, vol. 83, pp. 85-103, 2017. https://doi.org/10.1016/j.jbankfin.2017.06.010
  12. N. Al Aamery, J. F. Fox, M. Snyder, and C. V. Chandramouli, "Variance analysis of forecasted streamflow maxima in a wet temperate climate," Journal of Hydrology, vol. 560, pp. 364-381, 2018. https://doi.org/10.1016/j.jhydrol.2018.03.038
  13. A. B. Naik and A. C. Reddy, "Optimization of tensile strength in TIG welding using the Taguchi method and analysis of variance (ANOVA)," Thermal Science and Engineering Progress, vol. 8, pp. 327-339, 2018. https://doi.org/10.1016/j.tsep.2018.08.005
  14. I. S. Sobolev, A. N. Orekhov, T. Bratec, L. P. Rikhvanov, and N. P. Soboleva, "Variance-Correlation analysis in the exploration of hydrothermal (fluidogenous) deposits using surface gamma-ray spectrometry," Journal of Applied Geophysics, vol. 159, pp. 597-604, 2018. https://doi.org/10.1016/j.jappgeo.2018.10.007
  15. G. Jiang and W. Wang, "Error estimation based on variance analysis of k-fold cross-validation," Pattern Recognition, vol. 69, pp. 94-106, 2017. https://doi.org/10.1016/j.patcog.2017.03.025
  16. Y. Zhao, Y. Ming, X. Liu, E. Zhu, K. Zhao, and J. Yin, "Large-scale k-means clustering via variance reduction," Neurocomputing, vol. 307, pp. 184-194, 2018. https://doi.org/10.1016/j.neucom.2018.03.059
  17. A. M. Deylami and B. M. Asl, "Iterative minimum variance beamformer with low complexity for medical ultrasound imaging," Ultrasound in Medicine & Biology, vol. 44, no. 8, pp. 1882-1890, 2018. https://doi.org/10.1016/j.ultrasmedbio.2018.04.016
  18. Z. Jin, L. Min, M. K. Ng, and M. Zheng, "Image colorization by fusion of color transfers based on DFT and variance features," Computers & Mathematics with Applications, vol. 77, no. 9, pp. 2553-2567, 2019. https://doi.org/10.1016/j.camwa.2018.12.033
  19. G. Simarro, K. R. Bryan, R. M. Guedes, A. Sancho, J. Guillen, and G. Coco, "On the use of variance images for runup and shoreline detection," Coastal Engineering, vol. 99, pp. 136-147, 2015. https://doi.org/10.1016/j.coastaleng.2015.03.002
  20. X. Chen, A. Molina-Cristobal, M. D. Guenov, and A. Riaz, "Efficient method for variance-based sensitivity analysis," Reliability Engineering & System Safety, vol. 181, pp. 97-115, 2019. https://doi.org/10.1016/j.ress.2018.06.016
  21. M. I. Radaideh, S. Surani, D. O'Grady, and T. Kozlowski, "Shapley effect application for variance-based sensitivity analysis of the few-group cross-sections," Annals of Nuclear Energy, vol. 129, pp. 264-279, 2019. https://doi.org/10.1016/j.anucene.2019.02.002
  22. W. Yun, Z. Lu, K. Zhang, and X. Jiang, "An efficient sampling method for variance-based sensitivity analysis," Structural Safety, vol. 65, pp. 74-83, 2017. https://doi.org/10.1016/j.strusafe.2016.12.007
  23. H. Chen and H. Gao, "Unified recursion formula of k step original matrix in common discrete distribution," Journal of Hunan Business College, vol. 2002, no. 2, pp. 110-111, 2002.
  24. Q. Chen, "Discrete distribution's recursion formula of k-taped origin matrix," Statistics & Information Tribune, vol. 2000, no. 1, pp. 26-28, 2000.
  25. Q. Chen and Y. Ma, "Discrete distribution's recursion formula of k-taped central moment," Statistics & Information Tribune, vol. 1999, no. 2, pp. 36-38, 1999.
  26. C. G. Chen, "The counting method of k-order central moment of three kinds of discrete random variable," Journal of Jianghan University (Social Science Edition), vol. 2000, no. 6, pp. 66-68, 2000.
  27. S. Fan, "Recurrence formula calculating the statistics for changed sample size," Journal of Inner Mongolia Agricultural University (Natural Science Edition), vol. 11, no. 1, pp. 153-162, 1990.
  28. J. Liu and X. Sun, "Real-time calculation method of variance of non-zero mean measurement and control data," Mathematics Learning and Research, vol. 2016, no. 21, pp. 148-150, 2016.
  29. H. B. Deng, J. F. Liu, and Y. N. Wang, "Recursive algorithm for mean variance and its application," Computer and Modernization, vol. 1996, no. 4, pp. 9-11, 1996.
  30. A. S. Chen, H. C. Chang, and L. Y. Cheng, "Time-varying variance scaling: application of the fractionally integrated ARMA model," The North American Journal of Economics and Finance, vol. 47, pp. 1-12, 2019. https://doi.org/10.1016/j.najef.2018.11.007
  31. A. M. Chu, R. W. Li, and M. K. So, "Bayesian spatial-temporal modeling of air pollution data with dynamic variance and leptokurtosis," Spatial Statistics, vol. 26, pp. 1-20, 2018. https://doi.org/10.1016/j.spasta.2018.05.002
  32. Y. Yang and S. Wang, "Two simple tests of the trend hypothesis under time-varying variance," Economics Letters, vol. 156, pp. 123-128, 2017. https://doi.org/10.1016/j.econlet.2017.04.030
  33. J. Wang, L. Wang, and X. He, "The study of high accuracy time keeping based on FPGA when navigation satellite losing connection," Chinese Journal of Electron Devices, vol. 39, no. 1, pp. 140-143, 2016.