1. Introduction

High-dimensional spaces frequently occur in mathematics and the sciences, in example N-dimensional feature space, which presents input signals of neural network or collection of N-dimensional parameters for multidimensional data analysis. Rotation is one of rigid transformations in geometrical space, which preserves length of vectors and can be presented using matrix operation like Y = M.X, where X and Y are input and output vector respectively, and M is rotation matrix. This article proposes an N-dimensional rotation matrix generation algorithm for given input and output vector.

2. Definition of the Task

Let's say that we have two N-dimensional vectors X and Y, having the same dimension, X, Y ∈ R^N. We want to obtain a rotation matrix M that satisfies the equation.

(1)

where has the same norm as X and the same direction as Y, i.e. and

One of possibilities to generate rotation matrix M includes the following sequence of operations:

1) Obtain two orthogonal vectors in the plane, in which lies the two given vectors using Gramm-Schmidt procedure [2, 3, 16].

2) Enlarge this 2-dimensional basis to N- dimensional basis B2, in which given vectors X, Y are transformed

to and .

3) Create matrix of Givens rotation G(1, 2, θ) for R^N, which makes rotation of vector in -plane to the direction of vector

4) Obtaining rotation matrix M as

(2)

where P is matrix, which transforms initial basis B to basis B2.

Another way to generate rotation matrix M is to use Householder Reflection [4, 10, 17, 18]. If X and Y are vectors with the same norm there exists an orthogonal symmetric matrix P such that where and . Matrix P is matrix of reflection (not a rotation) because det P = -1, (which gives the name to method) that’s why to obtain matrix of rotation M, for which det M = 1, have to be performed two subsequent reflections. Matrix of rotation can be obtained as multiplication of two matrix of reflection P1 and P2 as M = P1.P2.

This article presents a new algorithm for generation of N-dimensional rotation matrix, which rotates given vector X to the direction of given vector Y. Algorithm, named N-dimensional Rotation Matrix Generation Algorithm (NRMG) includes the following sequence of operations:

1) Obtaining rotation matrix M_X, which rotates given vector X to the direction of axis

2) Obtaining rotation matrix M_Y, which rotates given vector Y to the direction of axis

3) Obtaining rotation matrix M as multiplication of M_X by inverse matrix of M_Y given as

Below this three operations will be described subsequently

3. Rotation of Given Vector X to the Direction of Axis x₁

Rotation of given vector X to the direction of one of coordinate axes (e.g. axis ) can be performed by subsequent multiplications by Givens matrices [1] as follow:

(3)

Givens matrices G(k, k+1, θk), k = N-1, n-2, … 1 are defined as follows [1, 2]:

(4)

where θk is the angle of rotation and coefficients Ck=cos( θk) and Sk=sin(θk) appears at the intersections of k-th and k+1 -th rows and columns.

Every one multiplication of vector by Givens matrix G(k, k+1, θk) performs rotation of its projection in coordinate plane (x_k, x_k+1), which changes values only of vector’s coordinates to . This multiplication can be presented as multiplication of coordinates by sub matrix A(k, k+1, θk) as follows:

(5)

Taking in consideration that multiplication with Givens matrix G(k, k+1, θk) changes only values of vector’s coordinates (to ), schema of multiplication by Givens matrix G(k, k+1, θk) can be presented as operator for two-dimensional rotation as follows:

Figure 1. Schema of two-dimensional rotation, performed by Givens matrix G(k, k+1, θk)

The target of multiplication by Givens matrix G(k, k+1, θk) is to set to zero coordinate It is easy to find that equation and equations (5) are satisfied simultaneously when and are calculated using formulas:

(6)

Thus searched matrix M_X can be calculated as multiplication of Givens matrices

as follows:

(7)

where coefficients of rotation and are calculated using formulas (6). Calculation of angles of two-dimensional rotations really is not needed. If then corresponding Givens matrix is equal to Identity matrix G(k, k+1, θk) = I – no rotation.

Schema for rotation of vector X to the direction of axis using two-dimensional rotations can be presented as follows:

Figure 2. Schema for rotation of vector X to the direction of axis

Every one block for two-dimensional rotation (as it was given on Fig. 3) presents rotation of two-dimensional vector to the direction of axis k=1,2,…N-1. This two-dimensional rotation is the base operation of proposed algorithm.

Figure 3. Block of base operation - rotation of two-dimensional vector to the direction of axis

As it can be seen from (3) and Fig. 2, rotation of N-dimensional vector to the direction of axis needs execution of N-1 subsequent base operations. Thus if one base operation has execution time Tb, then rotation of given N-dimensional vector X to the direction of axis will take execution time (N-1).Tb. As it is described below, this time can be reduced using parallel execution of base operations.

4. Description of NRMG Algorithm

NRMG algorithm for generation of N-dimensional rotation matrix M, which rotates given vector X to the direction of given vector Y consist the following operations:

1) Obtaining rotation matrix M_X, which rotates given vector X to the direction of axis

2) Obtaining rotation matrix M_Y, which rotates given vector Y to the direction of axis

3) Obtaining rotation matrix M, which rotates given vector X to the direction of given vector Y as multiplication of matrix M_X and inverse matrix of M_Y, as follows:

(8)

It is important to note that NRMG algorithm do not need vectors X and Y to have the same norm (as it is needed for Householder Reflection i.e.). Multiplication of given vector X by matrix of rotation M will give resultant vector , which will have norm of vector X, but direction of vector Y.

Time complexity of proposed algorithm depends of algorithm, used for calculation of coefficients and of two-dimensional base operations. This calculation depends of practical realization and is not a subject of this article.

NRMG algorithm can be used for different reversible calculations. An example that uses NRMG algorithm for transformation of images appears below (6).

5. Increasing Performance Using Parallel Execution of Two-Dimensional Rotations

Parallel execution of two-dimensional rotations (base operations of algorithm) is one way to increase calculation performance. This possibility is proposed in [7, 8] in relation of matrix decomposition. As this parallelism gives significant decrease of subsequent calculations, below will be presented one realization of this approach for proposed algorithm without pretensions of novelty.

Let’s have N-dimensional vector Vector X can be presented as a sum of two vectors X1 and X2, every one of which has half coordinates of value zero and half coordinates, that have the same values as the coordinates of given vector X, as follows:

(9)

Rotation of vector X to the direction of axis by multiplication with matrix of rotation M will give resultant vector X12_(N/2) which is the sum of rotated to the direction of axis vectors X1 and X2 as follows:

(10)

For zero coordinates of X1 and X2 corresponding matrices of base operations G(k, k+1, θk) are equal to identity matrix I (i.e. no rotation). This shows that coordinate planes, in which are rotated projections of X1 are different from those, in which are rotated X2. As a resultant vector we get:

(11)

where in second sum symbol for angle or rotation φ has been replaced with θ for convenience.

Vector X12_(N/2) has only two non-zero coordinates - x₁ and x_N/2+1, so it lie in coordinate plane . Vector X_(N/2) to the direction of axis can be obtained by only one two-dimensional rotation of vector X12_(N/2) in this coordinate plane as follows:

(12)

Schema below presents obtaining of vector X_(N/2) = [r_X, 0, …, 0]^T. using rotation of vector X12_(N/2) to the direction of axis

As it can be seen from (8)÷(10) and from schema on Fig. 4, after one division of given vector X the number of subsequent base operations is decreased to N/2 regardless that the number of base operations remain the same – N-1. It is easy to find that separation of given vector X to more then two parts will give more decreasing of subsequent base operations.

Figure 4. Schema for rotation of vector X, separated into two parts, to the direction of axis

The limit of subsequent divisions is reached when every one part has only two elements. In example if given vector has dimension N=8 it can be separated to 4 parts of two elements. Rotation of every one part of vector (as two-dimensional vector) to the direction of one of coordinates gives resultant vector, that has N/2 non-zero elements. The same way this sub-vector of dimension N/2 can be separated to N/4 parts of two elements and rotation of every one of this parts gives resultant vector with N/4 non-zero elements. It’s easy to find that if (set of all natural numbers) then the number of subsequent rotations, needed to obtain vector with only one non-zero element, is equal to log₂N.

Figure 5. Schema for accelerated rotation of 8-dimensional vector to the direction of axis

In example if vector X has dimension N=8, the number of needed subsequent rotations will be log₂8 = 3. Schema for accelerated rotation of 8-dimensional vector to the direction of axis will look as on figure above

It is important to note the following:

1) Accelerated rotation (AR) of given vector to the direction of axis can be applied not only for vectors, that have dimension N=2^P, P∈N, but for every one vector with dimension greater then 2. In example if N=7 then difference between schema of AR and those, given above, will be only this, that in first stage will miss the last base operation and x7 will go straight to base operation on second stage.

2) The number NR of stages (in which parallel execution of base operations of AR have to be performed) is equal to ⌈log₂N⌉ whereas number of all base operations is N-1 – the same as when all rotations are subsequent.

3) AR really increases calculation performance in case of parallel execution of base operations in stages. If base operations in stages are executed consecutively, the only advantage of AR is decreasing of accumulation of calculation errors (due to rounding e.g).

For high dimensional vectors AR proposes significant decreasing of subsequently executed base operations. In example if dimension of vectors is N=1024, the number of subsequently executed base operations is 1024-1, whereas AR algorithm uses number of stages (which defines the number of subsequent base operations) NStages = log₂1024 = 10.

It is important to note, that rotation is reversible linear operation, which mean that AR is reversible linear operation too. Reversibility of rotation, in particularly AR, is the “key stone” of proposed NRMG algorithm.

When AR is used, rotation matrix M_X and M_Y can be presented as a multiplication of matrices MS₁, MS₂, … MS_NR, which correspond to the stages of rotation, shown in Fig. 5. In example for vector with dimension N=8 matrices of stages MS₃.MS₂.MS₁ will look as in Fig. 6. where C_1,1, S_1,1, C_1,2, S_1,2, C_1,3, S_1,3, C_2,1, S_2,1,C_2,2, S_2,2, C_3,1, S_1,3 are denotation of and index i is the number of stage, and j is the number of base operation.

Figure 6. Matrices of stages for AR of 8-dimensional vector

As it can be seen, matrices of stages MSk, k=1, 2, …,⌈log₂N⌉ (except the last one) are not Givens matrices. They are matrices for parallel execution of two-dimensional rotations in corresponding coordinate planes as follows:

(13)

In NRMG that uses AR (which is not obligate), matrices of stages denote parallel execution of base operations. Schema, given below shows rotation of given 8-dimensional vector X to the direction of vector Y and obtaining rotation matrix M, which performs this rotation. Every one of matrices M_X and M_Y is calculated as multiplication of ⌈log₂N⌉ matrices of stages for which coefficients Ci-j and Si-j are calculated using (6).

6. Reversible Transformation of Images Using NRMG Algorithm

Down we will give one example of using NRMG algorithm for reversible image transformation.

Let’s have two monochrome raster images I1 and I2 which have the same number of pixels N. As it is known [14], raster images are presented as dot matrix data structure, so the two given images can be presented as two N-dimensional vectors X and Y, every element of which presents brightness of one of pixels. Using NMRG algorithm can be obtained rotation matrix M, which rotates vector X to the direction of vector Y. Since rotation do not change the norm of the vector, resultant vector will have the same norm as X. As a result, rotation will transform image I1 to one presentation of image I2, brightness of every one pixel of which is equal to the brightness of corresponding pixel of image I2, scaled with coefficient . If X and Y have the same norm, vectors and Y will be identical.

Example 1. Code of Matlab function for accelerated rotation of vector X to the direction of axis x1. Function returns matrix of rotation MX

Figure 7. Schema for rotation of 8-dimensional vector X to the direction of vector Y using NRMG algorithm and AR

Has been created Matlab program to test proposed NRMG algorithm. Program consist function for accelerated rotation fnAR and code, which uses this function to obtain matrix M, which rotates given vector X to the direction of given vector Y.

Code, that uses this function to obtain matrix M, which rotates given vector X to the direction of given vector Y is given below:

Example 2. Code of Matlab, which creates matrix of rotation using fnAR function

For test data has been used the following two images:

Figure 8. Test images

Images can be presented as 64-dimensional vectors as follows (written using Matlab Language syntax for row vectors):

X =[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0];

Y =[0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0];

Test program, given above, obtain vector Z to the direction of vector Y using NRMG algorithm, and compare vectors Z and Y. Program displays message “Z and Y are identical”, which shows that two vectors (and corresponding images) are identical at least with precision of 10^-6. It’s important to note, that vectors X and Y have the same norm.

7. Conclusions

In this article, we presents a new algorithm for generation of N-dimensional rotation matrix M, which rotates given N-dimensional vector X to the direction of given vector Y which has the same dimension. Also examined is the possibility to perform parallel calculation of base operations - two-dimensional rotations. Algorithm can be used for different reversible calculations. It is included one example of image transformation that uses NRMG algorithm.

Proposed NRMG algorithm proves that

1) Every one matrix of rotation M, which rotates given vector X to the direction of given vector Y can be presented as where M_X rotates vector X to the direction of one of coordinate axes (e.g. axis x₁) and M_Y rotates vector Y to the direction of the same coordinate axis.

2) Every one rotation of N-dimensional vector can be performed by 2(N-1) two-dimensional rotations in N-1 coordinate planes.

As an advantage of NRMG algorithm to known solutions, (shortly described in p. 2), can be pointed a possibility to realise it as Discrete Linear System, elements in which performs base operations. This possibility is a result of the locality of data, used for base operations and independence of base operations inside one stage of rotation.