An algorithm for arbitrary-order cumulant tensor calculation in a sliding window of data streams

Domino, Krzysztof ; Gawron, Piotr

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 1, pp. 195-206.

Résumé

High-order cumulant tensors carry information about statistics of non-normally distributed multivariate data. In this work we present a new efficient algorithm for calculation of cumulants of arbitrary orders in a sliding window for data streams. We show that this algorithm offers substantial speedups of cumulant updates compared with the current solutions. The proposed algorithm can be used for processing on-line high-frequency multivariate data and can find applications, e.g., in on-line signal filtering and classification of data streams. To present an application of this algorithm, we propose an estimator of non-Gaussianity of a data stream based on the norms of high order cumulant tensors. We show how to detect the transition from Gaussian distributed data to non-Gaussian ones in a data stream. In order to achieve high implementation efficiency of operations on super-symmetric tensors, such as cumulant tensors, we employ a block structure to store and calculate only one hyper-pyramid part of such tensors.

Détail

Keywords: high order cumulant, time series statistics, nonnormally distributed data, data streaming
Mots-clés : kumulant wysokiego rzędu, szereg czasowy, baza danych rozproszona, strumień danych

Bibliographie

[1] Arismendi Zambrano, J. and Kimura, H. (2014). Monte Carlo approximate tensor moment simulations, Numerical Linear Algebra with Applications, DOI: 10.2139/ssrn.2491639.

[2] Barndorff-Nielsen, O.E. and Cox, D.R. (1989). Asymptotic Techniques for Use in Statistics, Chapman Hall, London/New York, NY.

[3] Becker, H., Albera, L., Comon, P., Haardt, M., Birot, G., Wendling, F., Gavaret, M., Bénar, C.-G. and Merlet, I. (2014). EEG extended source localization: Tensor-based vs. conventional methods, NeuroImage 96: 143–157.

[4] Bezanson, J., Chen, J., Karpinski, S., Shah, V. and Edelman, A. (2014). Array operators using multiple dispatch: A design methodology for array implementations in dynamic languages, Proceedings of the ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, Edinburgh, UK, p. 56.

[5] Bezanson, J., Edelman, A., Karpinski, S. and Shah, V.B. (2017). Julia: A fresh approach to numerical computing, SIAM Review 59(1): 65–98.

[6] Bezanson, J., Karpinski, S., Shah, V.B. and Edelman, A. (2012). Julia: A fast dynamic language for technical computing, arXiv:1209.5145.

[7] Birot, G., Albera, L., Wendling, F. and Merlet, I. (2011). Localization of extended brain sources from EEG/MEG: The ExSo-MUSIC approach, NeuroImage 56(1): 102–113.

[8] Blaschke, T. and Wiskott, L. (2004). Cubica: Independent component analysis by simultaneous third-and fourth-order cumulant diagonalization, IEEE Transactions on Signal Processing 52(5): 1250–1256.

[9] Cherubini, U., Luciano, E. and Vecchiato, W. (2004). Copula Methods in Finance, John Wiley Sons, Chichester.

[10] Chevalier, P., Ferréol, A. and Albera, L. (2006). High-resolution direction finding from higher order statistics: The 2rmq-MUSIC algorithm, IEEE Transactions on Signal Processing 54(8): 2986–2997.

[11] Comtet, L. (1974). Advanced Combinatorics, Reidel Pub., Boston, MA.

[12] Domino, K. (2017). The use of the multi-cumulant tensor analysis for the algorithmic optimisation of investment portfolios, Physica A: Statistical Mechanics and Its Applications 467: 267–276.

[13] Domino, K. and Gawron, P. (2018). CumulantsUpdates.jl, Zenodo, DOI:10.5281/zenodo.1213205.

[14] Domino, K., Gawron, P. and Pawela, Ł. (2018a). Cummulants.jl, Zenodo, DOI:10.5281/zenodo.1185137.

[15] Domino, K., Pawela, Ł. and Gawron, P. (2017). SymmetricTensors.jl, Zenodo, DOI: 10.5281/zenodo.996222.

[16] Domino, K., Pawela, Ł. and Gawron, P. (2018b). Efficient computation of higer-order cumulant tensors, SIAM Journal on Scientific Computing 40(3): A1590–A1610.

[17] Gama, J. (2010). Knowledge Discovery from Data Streams, Chapman Hall/CRC Data Mining and Knowledge Discovery Series, Vol. 20103856, Chapman and Hall/CRC, Boca Raton, FL.

[18] Geng, M., Liang, H. and Wang, J. (2011). Research on methods of higher-order statistics for phase difference detection and frequency estimation, 4th International Congress on Image and Signal Processing (CISP), Shanghai, China, Vol. 4, pp. 2189–2193.

[19] Graham, R.L., Knuth, D.E. and Patashnik, O. (1989). Concrete Mathematics: A Foundation for Computer Science, Addison Wesley, Reading, MA.

[20] Hyvärinen, A. (2014). Independent component analysis of images, in D. Jaeger and R. Jung (Eds.), Encyclopedia of Computational Neuroscience, Springer, New York, NY, pp. 1–5.

[21] Jondeau, E., Jurczenko, E. and Rockinger, M. (2018). Moment component analysis: An illustration with international stock markets, Journal of Business Economic Statistics 36(4): 576–598, DOI: 10.1080/07350015.2016.1216851.

[22] Kendall, M.G. (1946). The Advanced Theory of Statistics, 2nd Edn., Charles Griffin and Co., London.

[23] Knuth, D.E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, Addison-Wesley Professional, Boston, MA.

[24] Latimer, J.R. and Namazi, N. (2003). Cumulant filters—a recursive estimation method for systems with non-Gaussian process and measurement noise, Proceedings of the 35th Southeastern Symposium on System Theory, Morgantown, WV, USA, pp. 445–449.

[25] Lukacs, E. (1970). Characteristics Functions, Griffin, London.

[26] Martin, I.W. (2013). Consumption-based asset pricing with higher cumulants, The Review of Economic Studies 80(2): 745–773.

[27] Qi, L. (2005). Eigenvalues of a real supersymmetric tensor, Journal of Symbolic Computation 40(6): 1302–1324.

[28] Rubinstein, M., Jurczenko, E. and Maillet, B. (2006). Multi-Moment Asset Allocation and Pricing Models, Vol. 399, John Wiley Sons, Chichester.

[29] Schatz, M.D., Low, T.M., van de Geijn, R.A. and Kolda, T.G. (2014). Exploiting symmetry in tensors for high performance: Multiplication with symmetric tensors, SIAM Journal on Scientific Computing 36(5): C453–C479.

[30] Sklar, A. (1959). Fonctions de répartition à n dimensions et leurs marges, Publications de l’Institut de Statistique de l’Université de Paris, Paris.

[31] Stefanowski, J., Krawiec, K. and Wrembel, R. (2017). Exploring complex and big data, International Journal of Applied Mathematics and Computer Science 27(4): 669–679, DOI: 10.1515/amcs-2017-0046.

[32] Virta, J., Nordhausen, K. and Oja, H. (2015). Joint use of third and fourth cumulants in independent component analysis, arXiv: 1505.02613.