Digital Signal Processing (DSP)-Oriented Reduced-Complexity Algorithms for Calculating Matrix–Vector Products with Small-Order Toeplitz Matrices

Digital Signal Processing (DSP)-Oriented Reduced-Complexity Algorithms for Calculating Matrix–Vector Products with Small-Order Toeplitz Matrices Janusz P. Papliński Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Żołnierska 49, 71-210 Szczecin, Poland http://orcid.org/0000-0002-6100-3913 Aleksandr Cariow Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Żołnierska 49, 71-210 Szczecin, Poland http://orcid.org/0000-0002-4513-4593 Paweł Strzelec Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Żołnierska 49, 71-210 Szczecin, Poland Marta Makowska Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Żołnierska 49, 71-210 Szczecin, Poland

Toeplitz matrix–vector products are used in many digital signal processing applications. Direct methods for calculating such products require N2 multiplications and N(N−1) additions, where N denotes the order of the Toeplitz matrix. In the case of large matrices, this operation becomes especially time intensive. However, matrix–vector products with small-order Toeplitz matrices are of particular interest because small matrices often serve as kernels in modern digital signal processing algorithms. Perhaps reducing the number of arithmetic operations when calculating matrix–vector products in the case of small Toeplitz matrices gives less effect than of large ones, but this problem exists, and it needs to be solved. The traditional way to calculate such products is to use the fast Fourier transform algorithm. However, in the case of small-order matrices, it is advisable to use direct factorization of Toeplitz matrices, which leads to a reduction in arithmetic complexity. In this paper, we propose a set of reduced-complexity algorithms for calculating matrix–vector products with Toeplitz matrices of order N=3,4,5,6,7,8,9. The main emphasis will be on reducing multiplicative complexity since multiplication in most cases is more time-consuming than addition. This paper also provides assessments of the implementation of the developed algorithms on FPGAs.
06 21 2024 417 437 signals5030021 https://creativecommons.org/licenses/by/4.0/ 10.3390/signals5030021 https://www.mdpi.com/2624-6120/5/3/21 https://www.mdpi.com/2624-6120/5/3/21/pdf 10.1007/978-3-0348-0612-1 Eidelman, Y., Gohberg, I., and Haimovici, I. (2014). Separable type representations of matrices and fast algorithms. Operator Theory: Advances and Applications, Birkhauser Springer. Neuts, M.F. (2021). Structured Stochastic Matrices of M/G/1 Type and Their Applications, CRC Press. 10.1090/conm/323 Olshevsky, V. (2003). Fast Algorithms for Structured Matrices: Theory and Applications: AMS-IMS-SIAM Joint Summer Research Conference on Fast Algorithms in Mathematics, Computer Science, and Engineering, 5–9 August 2001, Mount Holyoke College, South Hadley, Massachusetts, American Mathematical Soc.. Contemporary Mathematics. 10.1007/978-1-4612-0129-8 Pan, V. (2001). Structured Matrices and Polynomials: Unified Superfast Algorithms, Springer Science & Business Media. Yagle 22 fast algorithms for structured matrices in signal processing Handbook of Statist 1993 10.1016/S0169-7161(05)80088-4 Volume 10 933 Strang The discrete cosine transform, block Toeplitz matrices, and wavelets Advances in Computational Mathematics 1999 Volume 202 517 Haupt Toeplitz compressed sensing matrices with applicat ions to sparse channel estimation IEEE Trans. Inf. Theory 2010 10.1109/TIT.2010.2070191 56 5862 Chen Structured FISTA for image restoration Numer. Linear Algebra Appl. 2020 10.1002/nla.2278 27 2278 Hu A generalized structured low-rank matrix completion algorithm for mr image recovery IEEE Trans. Med. Imaging 2018 10.1109/TMI.2018.2886290 38 1841 Zhang Numerical algorithms for corner-modified symmetric Toeplitz linear system with applications to image encryption and decryption J. Appl. Math. Comput. 2023 10.1007/s12190-022-01819-7 69 1967 Moir Toeplitz matrices for lti systems, an illustration of their application to wiener filters and estimators Internat. J. Syst. Sci. 2018 10.1080/00207721.2017.1419306 49 800 Zhang Super-resolution surface mapping for scanning radar: Inverse filtering based on the fast iterative adaptive approach IEEE Trans. Geosci. Remote. Sens. 2017 10.1109/TGRS.2017.2743263 56 127 10.1137/1.9780898718850 Chan, R.H.-F., and Jin, X.-Q. (2007). An Introduction to Iterative Toeplitz Solvers, SIAM. 10.1109/WiMOB.2015.7347957 Goian, A., AlHajri, M.I., Shubair, R.M., Weruaga, L., Kulaib, A.R., AlMemari, R., and Darweesh, M. (2015, January 19–21). Fast detection of coherent signals using pre-conditioned root-music based on Toeplitz matrix reconstruction. Proceedings of the WiMob 2015: IEEE 11th International Conference on Wireless and Mobile Computing, Networking and Communications, Abu Dhabi, United Arab Emirates. Laskar A low complexity quantum simulation framework for Toeplitz-structured matrix and its application in signal processing IEEE Trans. Quantum Eng. 2023 10.1109/TQE.2023.3329213 4 1 Qiao Generalized nested sampling for compressing low rank Toeplitz matrices IEEE Signal Process. Lett. 2015 10.1109/LSP.2015.2438066 22 1844 Steimel Fast computation of Toeplitz forms under narrowband conditions with applications to statistical signal processing Signal Process. 1979 10.1016/0165-1684(79)90016-1 1 141 Chen Time series data for equipment reliability analysis with deep learning IEEE Access 2020 10.1109/ACCESS.2020.3000006 8 105484 Albu, F., and Fagan, A. (2003, January 9–12). The Gauss-Seidel pseudo affine projection algorithm and its application for echo cancellation. Proceedings of the Thrity-Seventh Asilomar Conference on Signals, Systems & Computers, Pacific Grove, CA, USA. Lu A survey on active noise control in the past decade—Part I: Linear systems Signal Process. 2021 10.1016/j.sigpro.2021.108039 183 108039 Wu A generalized leaky FxLMS algorithm for tuning the waterbed effect of feedback active noise control systems Mech. Syst. Signal Process. 2018 10.1016/j.ymssp.2017.12.021 106 13 Pan Novel systolization of subquadratic space complexity multipliers based on Toeplitz matrix–vector product approach IEEE Trans. Very Large Scale Integr. (Vlsi) Syst. 2019 10.1109/TVLSI.2019.2903289 27 1614 10.1145/3178291.3178292 Taşkin, H.K., and Cenk, M. (2018, January 22–25). Speeding up curve25519 using Toeplitz matrix-vector multiplication. Proceedings of the Fifth Workshop on Cryptography and Security in Computing Systems, HiPEAC, Manchester, UK. Ye A chaotic image cryptosystem based on Toeplitz and hankel matrices Imaging Sci. J. 2009 10.1179/136821909X12490307952919 57 266 Araujo, A. (2021). Building compact and robust deep neural networks with Toeplitz matrices. arXiv. 10.1609/aaai.v35i8.16824 Araujo, A., Negrevergne, B., Chevaleyre, Y., and Atif, J. (2021, January 2–9). On lipschitz regularization of convolutional layers using Toeplitz matrix theory. Proceedings of the AAAI Conference on Artificial Intelligence, Virtual. 10.1109/ICASSP.2019.8683556 Liao, S., Samiee, A., Deng, C., Bai, Y., and Yuan, B. (2019, January 12–17). Compressing deep neural networks using Toeplitz matrix: Algorithm design and fpga implementation. Proceedings of the ICASSP 2019: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brighton, UK. Liu Lu decomposition and Toeplitz decomposition of a neural network Appl. Comput. Harmon. Anal. 2024 10.1016/j.acha.2023.101601 68 101601 10.1109/ICASSP.2016.7472821 Lu, Z., Sindhwani, V., and Sainath, T.N. (2016, January 20–25). Learning compact recurrent neural networks. Proceedings of the ICASSP 2016 IEEE International Conference on Acoustics, Speech and Signal Processing, Shanghai, China. 10.1109/CVPR42600.2020.01152 Wang, J., Chen, Y., Chakraborty, R., and Yu, S.X. (2020, January 14–19). Orthogonal convolutional neural networks. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, Virtual. Wu A gridless DOA estimation method based on convolutional neural network with Toeplitz prior IEEE Signal Process. Lett. 2022 10.1109/LSP.2022.3176211 29 1247 Elvander Interpolation and extrapolation of Toeplitz matrices via optimal mass transport IEEE Trans. Signal Process. 2018 10.1109/TSP.2018.2866432 66 5285 10.1109/SAM53842.2022.9827806 Esfandiari, M., Vorobyov, S.A., and Heath, R.W. (2022, January 20–23). Sparsity enforcing with Toeplitz matrix reconstruction method for mmwave ul channel estimation with one-bit adcs. Proceedings of the 2022 IEEE 12th Sensor Array and Multichannel Signal Processing Workshop (SAM), Trondheim, Norway. Liu Trigonometric transform splitting methods for real symmetric Toeplitz systems Comput. Math. Appl. 2018 10.1016/j.camwa.2018.01.008 75 2782 Presti Boosting hankel matrices for face emotion recognition and pain detection Comput. Vis. Image Underst. 2017 10.1016/j.cviu.2016.10.007 156 19 10.3390/electronics12204268 Qi, B., Liu, X., Dou, D., Zhang, Y., and Hu, R. (2023). An enhanced doa estimation method for coherent sources via Toeplitz matrix reconstruction and Khatri–Rao subspace. Electronics, 20. 10.1007/978-1-4419-9226-0_17 Saeed, K. (2003). Object classification and recognition using Toeplitz matrices. Artificial Intelligence and Security in Computing Systems, Springer. Xu Machine learning for reliability engineering and safety applications: Review of current status and future opportunities Reliab. Eng. Syst. Saf. 2021 10.1016/j.ress.2021.107530 211 107530 Jiafeng, X., Chiou-Yng, L., and Pramod Kumar, M. (2019, January 26–29). Low-complexity systolic multiplier for GF (2 m) using Toeplitz matrix-vector product method. Proceedings of the 2019 IEEE International Symposium on Circuits and Systems (ISCAS), Sapporo, Japan. Chan Conjugate gradient methods for Toeplitz systems SIAM Rev. 1996 10.1137/S0036144594276474 38 427 Heinig Fast algorithms for Toeplitz and hankel matrices Linear Algebra Appl. 2011 10.1016/j.laa.2010.12.001 435 1 Hsue Fast algorithms for solving Toeplitz systems of equations using number-theoretic transforms Signal Process. 1995 10.1016/0165-1684(95)00017-8 44 89 Chen On the correlation matrix of the discrete fourier transform and the fast solution of large Toeplitz systems for long-memory time series J. Amer. Statist. Assoc. 2006 10.1198/016214505000001069 101 812 Dongarra Matrix-vector and matrix-matrix multiplications Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide 2000 Volume 11 320 Cariow Fast algorithms to compute matrix-vector products for Toeplitz and hankel matrices Electr. Rev. 2012 88 166 Beliakov, G. (2014). On fast matrix-vector multiplication with a hankel matrix in multiprecision arithmetics. arXiv. Karatsuba Multiplication of many-digital numbers by automatic computers Dokl. Akad. Nauk. Russ. Acad. Sci. 1962 145 293 Cariow Strategies for the synthesis of fast algorithms for the computation of the matrix-vector products J. Signal Process. Theory Appl. 2014 3 1 The ubiquitous kronecker product J. Comput. Appl. Math. 2000 10.1016/S0377-0427(00)00393-9 123 85 Ayres, F. (1962). Theory and Problems of Matrices, McGraw-Hill.