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

• Autorzy: Domino Krzysztof , Gawron Piotr

Identyfikatory

DOI

10.2478/amcs-2019-0015

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

high order cumulant; time series statistics; nonnormally distributed data; data streaming

PL

kumulant wysokiego rzędu; szereg czasowy; baza danych rozproszona; strumień danych

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2019
• Tom: Vol. 29, no. 1
• Strony: 195--206
• Opis fizyczny: Bibliogr. 32 poz., rys., tab., wykr.

Twórcy

autor

Domino Krzysztof

• Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland

autor

Gawron Piotr

• Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Bałtycka 5, 44-100 Gliwice, Poland

Bibliografia

• [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.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).