We consider a specific version of the authors’ approach to the synthesis of bases of discrete orthogonal transforms (DOTs). The approach takes into account the relation between the structure of basis functions of a transform and the existence of a certain numeral system on the (multidimensional) index set of the input signal. In contrast to Chernov’s prototype paper “Discrete orthogonal transforms with bases generated by self-similar sequences” (2018), which was concerned with DOTs associated with irredundant numeral systems (where each index of the input signal has a unique representation in a chosen numeral system), in the present paper we study the case of the so-called complete numeral systems. In this case, there is no bijection between the set of input indices of DOTs and the set of their digital representations. Potentially, such statements of applied problems naturally appear in image recognition, artificial intelligence, theory of formal languages, mathematical programming, and other areas where the analyzed objects are characterized by many heterogeneous attributes, which can be quantitative, qualitative, and mixed. There may be several copies of each objects, and the copies may have inconsistent descriptions, which must be considered and analyzed as a whole. Such objects with many attributes can be represented as multisets (“sets with repetitions”). Since discrete spectral analysis is a basic tool for solving the described problems in the classical "multiple” interpretation of objects, we try to extend some ideas and methods of spectral analysis to the case of multiset objects.
Keywords: multisets, discrete orthogonal transformations, complete sequences
Received April 14, 2020
Revised June 23, 2020
Accepted July 27, 2020
Funding Agency: This work was supported by the Ministry of Science and Higher Education of the Russian Federation within the state assignment to the Federal Research Center “Crystallography and Photonics” of the Russian Academy of Sciences (agreement no. 007-GZ/Ch3363/26) in studying numeral systems and by the Russian Foundation for Basic Research (project nos. 19-07-00357_a and 18-29-03135) in studying machine arithmetics.
Vladimir Mikhailovich Chernov, Dr. Phys.-Math. Sci., Prof., Image Processing Systems Institute of the Russian Academy of Sciences — Branch of the Federal Scientific Research Center Crystallography and Photonics of Russian Academy of Sciences, Samara, 443001 Russia; Samara National Research University, Samara, 443086 Russia, e-mail: schraube@samtel.ru
Marina Aleksandrovna Chicheva, Cand. Sci. (Phys.-Math), Image Processing Systems Institute of the Russian Academy of Sciences — Branch of the Federal Scientific Research Center Crystallography and Photonics of Russian Academy of Sciences, Samara, 443001 Russia; Samara National Research University, Samara, 443086 Russia, e-mail: mchi@geosamara.ru
REFERENCES
1. Petrovskii A.B. Prostranstva mnozhestv i mul’timnozhestv [Spaces of sets and multisets]. Moscow: Editorial URSS, 2003. 248 p. ISBN: 5-354-00486-1 .
2. Petrovskii A.B. Teoriya izmerimykh mnozhestv i mul’timnozhestv [Theory of measurable sets and multisets]. Moscow: Nauka Publ., 2018, 359 p. ISBN: 978-5-02-040124-2 .
3. Aigner M. Combinatorial theory. N Y: Springer-Verlag, 1979, 483 p. doi: 10.1007/978-1-4615-6666-3 . Translated to Russian under the title Kombinatornaya teoriya. Moscow: Mir Publ., 1982. 558 p.
4. Stechkin B.S., Baranov V.I. Extremal combinatorial problems and their applications. Dordrecht: Springer, 1995, 210 p. doi: 10.1007/978-0-585-29602-9 . Original Russian text published in Stechkin B.S., Baranov V.I. Ekstremal’nye kombinatornye zadachi i ikh prilozheniya. Moscow: Nauka Publ., 1989. 240 p.
5. Chernov V.M. Discrete orthogonal transforms with bases generated by self-similar sequences. Computer Optics, 2018, vol. 42, no. 5, pp. 904–911 (in Russian). doi: 10.18287/2412-6179-2018-42-5-904-911
6. Chernov V.M. Some spectral properties of fractal curves. Machine Graphics & Vision, 1996, vol. 5, no. 1/2, pp. 413–422.
7. Chernov V.M. Tauber theorems for Dirichlet series and fractals. Proc. of ICPR’96, Vienna, 1996, vol. 2, Track B, pp. 656–661. doi: 10.1109/ICPR.1996.546905
8. Brown J.L. Note on complete sequences of integers. The American Mathematical Monthly, 1961, vol. 68, no. 6, pp. 557–560. doi: 10.2307/2311150
9. Pillai S.S. An arithmetical function concerning primes. Annamalai University Journal, 1930, pp. 159–167.
10. The On-Line Encyclopedia of Integer Sequences (OEIS). Available at: https://oeis.org/
11. Feinberg M. Fibonacci-Tribonacci. The Fibonacci quarterly, 1963, vol. 1(30), pp. 71–74.
12. Noe T.D. Primes in Fibonacci $n$-step and Lucas $n$-step sequences. J. Integer Seq., 2005, vol. 8, art.-no. 05.4.4, 12 p.
13. Moore T.L. Using Euler’s formula to solve plane separation problems. The College Mathematics Journal, 1991, vol. 22, no. 2, pp. 125–130. doi: 10.2307/2686448
14. Steiner J. A Few Statements about the Division of the Plane and of Space. J. Reine Angew. Math., 1826, no. 1, pp. 349–364 (in German). doi: 10.1515/crll.1826.1.349
Cite this article as: V.M. Chernov, M.A. Chicheva. Discrete orthogonal transforms on multisets associated with complete sequences, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 249–257; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2021, Vol. 313, Suppl. 1, pp. S33–S39.
