Multi-Dimensional Definition of Convolution
Abstract
Convolution is an indispensable operation for solving problems from a variety of subject areas: machine learning problems, data analysis, signal processing, image processing filters. However, due to the complexity of the algorithms that implement them, in practice, even three-dimensional convolutions are used much less often than one-and two-dimensional ones. The main reason for this lies in the absence of a single strict definition of the operation and the overload of the term “convolution” in mathematics. The multidimensional matrix algebra includes operations that are semantically similar to convolutions, and it is easily parallelized using natural generalizations of operations on flat matrices to the multidimensional case and has already proved its effectiveness in tensor algebra. Therefore, it is advisable to construct the definition of convolution through operations on the algebra of multidimensional matrices. The article considers an approach to improving the efficiency of convolution algorithms in software systems based on it, including convolutional neural networks. The author proposes a multidimensional matrix definition of the convolution operation. On its basis, a multidimensional matrix model of calculations is built, which will allow us to effectively formalize problems whose solution uses multidimensional convolution operations, as well as to implement an effective solution to these problems due to the natural parallelism inherent in the operations of the algebra of multidimensional matrices. As a result, a mathematical model of convolution operations based on the algebra of multidimensional matrices with the operation the (0, µ)-convolution product is obtained. In practice, in solving applied problems, the proposed mathematical model of convolution operations serves as the basis for developing libraries of programs that effectively implement these operations by parallelizing the operation the (0, µ)-convolution product.
References
2. Liskov B., Zilles S. Programming with abstract data types. ACM SIGPLAN Notices. 1974; 9(4):50-59. (In Eng.) DOI: https://doi.org/10.1145/942572.807045
3. Baroody A.J., DeWitt D.J. An object-oriented approach to database system implementation. ACM Transactions on Database Systems. 1981; 6(4):576-601. (In Eng.) DOI: https://doi.org/10.1145/319628.319645
4. Barford L. Filtering of Randomly Sampled, Time-Stamped Measurements. 2006 IEEE Instrumentation and Measurement Technology Conference Proceedings. IEEE Press, Sorrento, Italy; 2006. p. 1021-1026. (In Eng.) DOI: https://doi.org/10.1109/IMTC.2006.328336
5. Agarwal R., Burrus C. Fast one-dimensional digital convolution by multidimensional techniques. IEEE Transactions on Acoustics, Speech, and Signal Processing. 1974; 22(1):1-10. (In Eng.) DOI: https://doi.org/10.1109/TASSP.1974.1162532
6. Chen Y., Dai X., Liu M., Chen D., Yuan L., Liu Z. Dynamic Convolution: Attention Over Convolution Kernels. 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE Press, Seattle, WA, USA; 2020. p. 11027-11036. (In Eng.) DOI: https://doi.org/10.1109/CVPR42600.2020.01104
7. Marshalko D.A., Kubanskih O.V. Convolutional Neural Network Architecture. Scientific notes of the Bryansk State University. 2019; (4):10-13. Available at: https://www.elibrary.ru/item.asp?id=42222091 (accessed 19.06.2021). (In Russ., abstract in Eng.)
8. Kanopoulos N., Vasanthavada N., Baker R.L. Design of an image edge detection filter using the Sobel operator. IEEE Journal of Solid-State Circuits. 1988; 23(2):358-367. (In Eng.) DOI: https://doi.org/10.1109/4.996
9. Gao W., Zhang X., Yang L., Liu H. An improved Sobel edge detection. 2010 3rd International Conference on Computer Science and Information Technology. IEEE Press, Chengdu; 2010. p. 67-71. (In Eng.) DOI: https://doi.org/10.1109/ICCSIT.2010.5563693
10. Chaple G., Daruwala R.D. Design of Sobel operator based image edge detection algorithm on FPGA. 2014 International Conference on Communication and Signal Processing. IEEE Press, Melmaruvathur, India; 2014. p. 788-792. (In Eng.) DOI: https://doi.org/10.1109/ICCSP.2014.6949951
11. Ottaviani G. Introduction to the Hyperdeterminant and to the Rank of Multidimensional Matrices. In: Ed. by I. Peeva. Commutative Algebra. Springer, New York, NY; 2013. p. 609-638. (In Eng.) DOI: https://doi.org/10.1007/978-1-4614-5292-8_20
12. Goncharov E., Iljin P., Munerman V. Multidimensional Matrix Algebra Versus Tensor Algebra or μ > 0. 2020 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). IEEE Press, St. Petersburg and Moscow, Russia; 2020. p. 1949-1954. (In Eng.) DOI: https://doi.org/10.1109/EIConRus49466.2020.9039478
13. Afanasyeva Z.S., Afanasyev A.D. Signature Detection and Identification Algorithm with CNN, Numpy and OpenCV. In: Ed. by R. Silhavy, P. Silhavy, Z. Prokopova. Software Engineering Perspectives in Intelligent Systems. CoMeSySo 2020. Advances in Intelligent Systems and Computing. 2020; 1295:467-479. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-63319-6_43
14. Yuan L., Qu Z., Zhao Y., Zhang H., Nian Q. A convolutional neural network based on TensorFlow for face recognition. 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC). IEEE Press, Chongqing, China; 2017. p. 525-529. (In Eng.) DOI: https://doi.org/10.1109/IAEAC.2017.8054070
15. Jayalakshmi G.S., Kumar V.S. Performance analysis of Convolutional Neural Network (CNN) based Cancerous Skin Lesion Detection System. 2019 International Conference on Computational Intelligence in Data Science (ICCIDS). IEEE Press, Chennai, India; 2019. p. 1-6. (In Eng.) DOI: https://doi.org/110.1109/ICCIDS.2019.8862143
16. Kumar N.K., Vigneswari D., Mohan A., Laxman K., Yuvaraj J. Detection and Recognition of Objects in Image Caption Generator System: A Deep Learning Approach. 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS). IEEE Press, Coimbatore, India; 2019. p. 107-109. (In Eng.) DOI: https://doi.org/10.1109/ICACCS.2019.8728516
17. Hung K.-W., Zhang Z., Jiang J. Real-Time Image Super-Resolution Using Recursive Depthwise Separable Convolution Network. IEEE Access. 2019; 7:99804-99816. (In Eng.) DOI: https://doi.org/10.1109/ACCESS.2019.2929223
18. Maggiori E. High-resolution aerial image labeling with convolutional neural networks. IEEE Transactions on Geoscience and Remote Sensing. 2017; 55(12):7092-7103. (In Eng.) DOI: https://doi.org/10.1109/TGRS.2017.2740362
19. Goncharov E., Munerman V., Yakovlev G. Software and Hardware Complex for Calculating Convolutions by Methods Multidimensional Matrix Algebra. 2021 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (ElConRus). IEEE Press, St. Petersburg, Moscow, Russia; 2021. p. 2176-2180. (In Eng.) DOI: https://doi.org/10.1109/ElConRus51938.2021.9396584
20. Zakharov V.N., Munerman V. I. Parallel'nyj algoritm umnozhenija mnogomernyh matric [Parallel Algorithm for Multidimensional Matrix Multiplication]. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2015; 11(2):384-390. Available at: https://www.elibrary.ru/item.asp?id=26167519 (accessed 19.06.2021). (In Russ., abstract in Eng.)
21. Mohamed K.S. Parallel Computing: OpenMP, MPI, and CUDA. Neuromorphic Computing and Beyond. Springer, Cham; 2020. p. 63-93. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-37224-8_3
22. Vetter J.S., et al. Keeneland: Bringing Heterogeneous GPU Computing to the Computational Science Community. Computing in Science & Engineering. 2011; 13(5):90-95. (In Eng.) DOI: https://doi.org/10.1109/MCSE.2011.83
23. Goncharov E.I., Munerman V.I., Samoylova T.A. The Method of Selecting Parameters of Multidimensional Matrix for Hill Encryption Algorithm. Sistemy komp’yuternoj matematiki i ih prilozheniya = Computer Mathematics Systems and Their Applications. 2019; (20-1):111-116. Available at: https://www.elibrary.ru/item.asp?id=39103166 (accessed 19.06.2021). (In Russ., abstract in Eng.)
24. Munerman V.I., Samoylova T.A. Algebraic Approach to Algorithmization of Routing Problems. Highly Available Systems. 2018; 14(5):50-56. (In Russ., abstract in Eng.) DOI: https://doi.org/10.18127/j20729472-201805-08
25. Munerman V.I. Construction of hardware-software complexes architecture to improve massively data processing. Highly Available Systems. 2014; 10(4):3-16. Available at: https://www.elibrary.ru/item.asp?id=22831892 (accessed 19.06.2021). (In Russ., abstract in Eng.)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Publication policy of the journal is based on traditional ethical principles of the Russian scientific periodicals and is built in terms of ethical norms of editors and publishers work stated in Code of Conduct and Best Practice Guidelines for Journal Editors and Code of Conduct for Journal Publishers, developed by the Committee on Publication Ethics (COPE). In the course of publishing editorial board of the journal is led by international rules for copyright protection, statutory regulations of the Russian Federation as well as international standards of publishing.
Authors publishing articles in this journal agree to the following: They retain copyright and grant the journal right of first publication of the work, which is automatically licensed under the Creative Commons Attribution License (CC BY license). Users can use, reuse and build upon the material published in this journal provided that such uses are fully attributed.
