Geodesic
On the complexity and dimension of continuous finite-dimensional maps
Teoriâ veroâtnostej i ee primeneniâ, Tome 65 (2020) no. 3, pp. 479-497 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We introduce the concept of $\varepsilon$-complexity of an individual continuous finite-dimensional map. This concept is in good accord with the principle of A. N. Kolmogorov's idea of measuring complexity of objects. It is shown that the $\varepsilon$-complexity of an “almost all” Hölder map can be effectively described. This description can be used as a basis for a model-free technique for segmentation and classification of data of arbitrary nature. A new definition of the dimension of the graph of a map is also proposed.
Keywords: $\varepsilon$-complexity, continuous maps, model-free classification and segmentation of data. 
@article{TVP_2020_65_3_a2,
     author = {B. S. Darkhovsky},
     title = {On the complexity and dimension of continuous finite-dimensional maps},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {479--497},
     year = {2020},
     volume = {65},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TVP_2020_65_3_a2/}
}
TY  - JOUR
AU  - B. S. Darkhovsky
TI  - On the complexity and dimension of continuous finite-dimensional maps
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2020
SP  - 479
EP  - 497
VL  - 65
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TVP_2020_65_3_a2/
LA  - ru
ID  - TVP_2020_65_3_a2
ER  - 
%0 Journal Article
%A B. S. Darkhovsky
%T On the complexity and dimension of continuous finite-dimensional maps
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2020
%P 479-497
%V 65
%N 3
%U http://geodesic.mathdoc.fr/item/TVP_2020_65_3_a2/
%G ru
%F TVP_2020_65_3_a2
B. S. Darkhovsky. On the complexity and dimension of continuous finite-dimensional maps. Teoriâ veroâtnostej i ee primeneniâ, Tome 65 (2020) no. 3, pp. 479-497. http://geodesic.mathdoc.fr/item/TVP_2020_65_3_a2/

[1] A. N. Shiryaev, Stochastic disorder problems, Probab. Theory Stoch. Model., 93, Springer, Cham, 2019, xix+397 pp. | DOI | MR | Zbl

[2] T. M. Cover, J. A. Thomas, Elements of information theory, 2nd ed., Wiley-Interscience [John Wiley Sons], Hoboken, NJ, 2006, xxiv+748 pp. | DOI | MR | Zbl

[3] Ya. G. Sinai, Introduction to ergodic theory, Math. Notes, 18, Princeton Univ. Press, Princeton, NJ, 1976, 144 pp. | MR | Zbl

[4] A. N. Kolmogorov, “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Math. Surveys, 38:4 (1983), 29–40 | DOI | MR | Zbl

[5] A. Shen, V. A. Uspensky, N. Vereshchagin, Kolmogorov complexity and algorithmic randomness, Math. Surveys Monogr., 220, Amer. Math. Soc., Providence, RI, 2017, xviii+511 pp. | DOI | MR | Zbl

[6] B. Ryabko, J. Astola, M. Malyutov, Compression-based methods of statistical analysis and prediction of time series, Springer, Cham, 2016, ix+144 pp. | DOI | MR | Zbl

[7] R. Cilibrasi, P. M. B. Vitanyi, “Clustering by compression”, IEEE Trans. Inform. Theory, 51:4 (2005), 1523–1545 | DOI | MR | Zbl

[8] E. E. Demidov, Yu. V. Darevskaya, O. A. Morenkov, A. A. Tovchigrechko, “Nelineinyi korrelyatsionnyi analiz”, Obozrenie prikladnoi i promyshlennoi matematiki, 6:1 (1999), 4–57 | Zbl

[9] A. N. Kolmogorov, V. M. Tikhomirov, “$\varepsilon$-entropy and $\varepsilon$-capacity of sets in function spaces”, Amer. Math. Soc. Transl. Ser. 2, 17, Amer. Math. Soc., Providence, RI, 1961, 227–364 | MR | MR | Zbl | Zbl

[10] A. N. Kolmogorov, “Razlichnye podkhody k otsenke trudnosti priblizhennogo zadaniya i vychisleniya funktsii”, Proceedings of the international congress of mathematicians (Stockholm, 1962), Inst. Mittag-Leffler, Djursholm, 1963, 352–356 | MR | Zbl

[11] Ju. Ofman, “On the approximate realization of continuous functions on automata”, Soviet Math. Dokl., 4 (1963), 1439–1443 | MR

[12] S. S. Marchenkov, “Ob odnom metode analiza superpozitsii nepreryvnykh funktsii”, Problemy kibernetiki, 37, Nauka, M., 1980, 5–17 | MR | Zbl

[13] E. A. Asarin, “On convergence of uniform approximations of continuous functions”, Russian Math. Surveys, 39:3 (1984), 179–193 | DOI | MR | Zbl

[14] B. S. Darkhovskii, A. Ya. Kaplan, S. L. Shishkin, “On an approach to the estimation of the complexity of curves (using as an example an electroencephalogram of a human being)”, Autom. Remote Control, 63:3 (2002), 468–474 | DOI | Zbl

[15] B. S. Darhovsky, A. Piryatinska, “New approach to the segmentation problem for time series of arbitrary nature”, Proc. Steklov Inst. Math., 287:1 (2014), 54–67 | DOI | DOI | MR | Zbl

[16] K. Falconer, Fractal geometry. Mathematical foundations and applications, 2nd ed., John Wiley Sons, Inc., Hoboken, NJ, 2003, xxviii+337 pp. | DOI | MR | Zbl

[17] T. Higuchi, “Approach to an irregular time series on the basis of the fractal theory”, Phys. D, 31:2 (1988), 277–283 | DOI | MR | Zbl

[18] B. E. Brodsky, B. S. Darkhovsky, Non-parametric statistical diagnosis: problems and methods, Math. Appl., 509, Kluwer Acad. Publ., Dordrecht, 2000, xvi+452 pp. | DOI | MR | Zbl

[19] B. Darkhovsky, A. Piryatinska, “Model-free offline change-point detection in multidimensional time series of arbitrary nature via $\varepsilon$-complexity: simulations and applications”, Appl. Stoch. Models Bus. Ind., 34:5 (2018), 633–644 | DOI | MR | Zbl

[20] A. Piryatinska, B. Darkhovsky, A. Kaplan, “Binary classification of multichannel-EEG records based on the $\varepsilon$-complexity of continuous vector functions”, Computer Methods and Programs in Biomedicine, 152 (2017), 131–139 | DOI