In this article, we analyze algorithmic ways to reduce the arithmetic complexity of calculating quaternion-valued linear convolution and also synthesize a new algorithm for calculating this convolution. During the synthesis of the discussed algorithm, we use the fact that quaternion multiplication may be represented as a matrix-vector product. The matrix participating in the product has unique structural properties that allow performing its advantageous decomposition. Namely, this decomposition leads to reducing the multiplicative complexity of computations. In addition, we used the fact that when calculating the elements of the quaternion-valued convolution, the part of the calculations of all matrix-vector products is common. It gives an additional reduction in the number of additions of real numbers and, consequently, a decrease in the additive complexity of calculations. Thus, the use of the proposed algorithm will contribute to the acceleration of calculations in quaternion-valued convolution neural networks.
5 November 2021 in IEEE Transactions on Neural Networks and Learning Systems
This brief presents the results of a study of the possibilities of reducing the arithmetic complexity of computing basic operations in octonionic neural networks and also proposes new algorithmic solutions for efficiently performing these operations. Here, we primarily mean the operation of multiplying octonions, the operation of computing the dot product of two octonion-valued vectors, and the operation of multiple multiplications of an octonion by several other octonions. In order to reduce the computational complexity of these operations, it is proposed to use the fast Walsh-Hadamard transform, which is well known in digital signal processing. Using this transform reduces the number of multiplications and additions of real numbers required to perform computations. Thus, the use of the proposed algorithms will speed up computations in octonion-valued neural networks.
4 February 2017 in Circuits, Systems, and Signal Processing
This paper proposes an effective approach to the computation of the discrete fractional Fourier transform for an input vector of any length N. This approach uses specific structural properties of the discrete fractional Fourier transformation matrix. Thanks to these properties, the fractional Fourier transformation matrix can be decomposed into a sum of three or two matrices, one of which is a dense matrix, and the rest of the matrix components are sparse matrices. The aforementioned dense matrix has unique structural properties that allow advantageous factorization. This factorization is the main contributor to the reduction in the overall computational complexity of the discrete fractional Fourier transform computation. The remaining calculations do not contribute significantly to the total amount of computation. Thus, the proposed approach allows to reduce the number of arithmetic operations when calculating the discrete fractional Fourier transform.
This paper proposes a new method for calculating the quaternion discrete Fourier transform for one-dimensional data. Although the computational complexity of the proposed method still belongs to the class, it allows us to reduce the total number of arithmetic operations required to perform it compared to other known methods for computing this transform. Moreover, compared to the method using symplectic decomposition, the presented method does not require changing the basis in the subspace of pure quaternions and, consequently, calculating the new basis vectors and change-of-basis matrix.