JP2008521294A - Eigenvalue decomposition and singular value decomposition of matrix using Jacobi rotation - Google Patents

Abstract

Techniques for decomposing a matrix using Jacobi rotation are described. To eliminate off-diagonal elements in the first matrix, a plurality of Jacobi rotation iterations are performed on the first matrix of complex values using a plurality of complex-valued Jacobi rotation matrices. A sub-matrix may be formed based on the first matrix at each iteration and is decomposed to obtain eigenvectors for the sub-matrix. A Jacobi rotation matrix may then be formed using the eigenvectors and may be used to update the first matrix. A second matrix of complex values containing orthogonal vectors is derived based on the Jacobi rotation matrix. For eigenvalue decomposition, a third matrix of eigenvalues may be derived based on the Jacobi rotation matrix. For singular value decomposition, the fourth matrix of left singular vectors and the matrix of singular values may be derived based on the Jacobi rotation matrix.

Description

  The present invention relates generally to communication, and more particularly to techniques for decomposing a matrix.

  A multiple-input multiple-output (MIMO) communication system employs multiple (T) transmit antennas at a transmitting station and multiple (R) receive stations at a receiving station for data transmission. A MIMO channel formed by T transmit antennas and R receive antennas may be decomposed into S spatial channels. However, S ≦ min {T, R}. The S spatial channels may be used to transmit data in such a way as to obtain higher overall throughput and / or greater reliability.

MIMO channel response is R × T channel response matrix

May be characterized. This matrix includes complex channel gains for all of the different pairs of transmit and receive antennas.

Channel response matrix

May be a diagonal matrix to obtain the eigenmode of S. The eigenmode of S may be viewed as an orthogonal spatial channel of the MIMO channel. Improved performance may be achieved by transmitting data in the eigenmode of the MIMO channel.

Channel response matrix

Is

Perform singular value decomposition of or

Depending on whether eigenvalue decomposition of the correlation matrix is performed, a diagonal matrix may be used. Singular value decomposition supplies left and right singular vectors, and eigenvalue decomposition supplies eigenvectors. The transmitting station transmits data to the S eigenmode using the right singular value vector or eigenvector. The receiving station receives data transmitted in the eigenmode of S using the left singular vector or eigenvector.

  Eigenvalue decomposition and singular value decomposition are very computationally intensive. Therefore, there is a need for techniques to efficiently decompose the matrix.

  This patent application is assigned to the assignee of this patent application and is filed on November 15, 2004, “Eigenvalue Decomposition and Singular Value Decomposition Using Jacobi Rotation” (Eigenvalue Decomposition). Claims priority to US Provisional Application No. 60 / 628,324 entitled Decomposition and Singular Value Decomposition of Matrices Using Jacobi Rotation.

  Techniques for efficiently decomposing a matrix using Jacobi rotation are described herein. These techniques may be used for eigenvalue decomposition of a complex-valued Hermitian matrix to obtain a matrix of eigenvectors and a matrix of eigenvalues for the Hermitian matrix. This technique may also be used for singular value decomposition of an arbitrary matrix of complex values to obtain a matrix of left singular vectors, a matrix of right singular vectors, and a matrix of singular values of any matrix. .

In one embodiment, multiple iterations of Jacobi rotation are performed on the first matrix of complex values using a plurality of complex-valued Jacobi rotation matrices to eliminate off-diagonal elements in the first matrix. The first matrix is the channel response matrix

,

Is

Correlation matrix, or other matrix. For each iteration, a submatrix may be formed based on the first matrix and may be decomposed to obtain eigenvectors for the submatrix. The Jacobi rotation matrix may be formed with eigenvectors and may be used to update the first matrix. A second matrix of complex values is derived based on the Jacobi rotation matrix. The second matrix includes orthogonal vectors;

A singular vector or

Matrix of eigenvectors of

It may be.

For eigenvalue decomposition, a third matrix of eigenvalues

May be derived based on the Jacobi rotation matrix. In the case of singular value decomposition based on the first singular value decomposition (SVD) embodiment, a third matrix of complex values

May be derived based on the Jacobi rotation matrix. Fourth matrix with orthogonal vectors

Is the third matrix

You may derive based on. And a matrix of singular values

Is also the third matrix

You may derive based on. In the case of singular value decomposition based on the second SVD embodiment, a matrix of orthogonal vectors and singular values

A third matrix with

May be derived based on the Jacobi rotation matrix.

  Various aspects and embodiments of the invention are described in further detail below.

  The term “exemplary” is used herein to mean serving as an example, instance, or illustration. Any embodiment described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments.

  The matrix decomposition techniques described herein include single carrier communication systems with single frequency subbands, multicarrier communication systems with multiple subbands, single carrier frequency division multiple access with multiple subbands ( It may be used for various communication systems such as SC = FDMA) systems and other communication systems. Multiple subbands may be obtained using orthogonal frequency division multiplexing (OFDM), other modulation techniques, or other configurations. OFDM divides the overall system bandwidth into multiple (K) orthogonal subbands. Orthogonal subbands are also called tones, subcarriers, bins, etc. For OFDM, each subband is associated with a respective subcarrier that may be modulated with data. SC-FDMA systems may utilize interleaved FDMA (IFDMA) to transmit to subbands distributed over the system bandwidth. Alternatively, local FDMA (LFDMA) may be used to transmit to adjacent subband blocks. Alternatively, enhanced FDMA (EFDMA) may be utilized to transmit to multiple blocks of adjacent subbands. In general, modulation symbols are sent in the frequency domain with OFDM and in the time domain with SC-FDMA. For clarity, much of the description below is for a MIMO system with a single subband.

The MIMO channel formed by multiple (T) transmit antennas and multiple (R) receive antennas is an R × T channel response matrix.

May be characterized. This may be given as:

However, i = 1,. . . R and j = 1,. . . The entry Hi, j for T indicates the coupling or complex channel gain between transmit antenna j and receive antenna i.

Channel response matrix

Is a diagonal matrix,

Multiple (S) channel responses may be obtained. However, S ≦ min {T, R}. For example, diagonalization is

Singular value decomposition of or

This may be achieved by performing eigenvalue decomposition of the correlation matrix.

The eigenvalue decomposition may be expressed as follows:

However,

Is

This is a T × T correlation matrix.

Is
Column

It is a T × T unitary matrix that is an eigenvector.

Is

Is a T × T diagonal matrix of eigenvalues.

Indicates conjugate transposition. Unitary matrix

Is characteristic

Is characterized by However,

Is a unit matrix. The columns of the unitary matrix are orthogonal to each other. Each column has unit power. Diagonal matrix

Contains possible non-zero values along the diagonal, and zero somewhere else.

The diagonal element of

Is the eigenvalue of. These eigenvalues are {λ1, λ2,. . . , Λs},

Represents the power gain for the eigenmode.

The non-diagonal element has the following characteristics

Is a Hermitian matrix. However,

Represents a complex conjugate.

Singular value decomposition may be expressed as:

However,

Is

Is an R × R unitary matrix of left singular vectors.

Is

Is an R × T diagonal matrix of singular values.

Is

Is a T × T unitary matrix of right singular values.

Each contain orthogonal vectors. Equations (2) and (3) are

The right singular vector of

This is also the eigenvector of.

The diagonal element of

The singular value of These singular values are {σ ₁ , σ ₂ ,. . . σ _s },

Represents the channel gain of the eigenmode.

The singular value of

Is also the square root of the eigenvalue of

It is.

Sending station

Using singular vectors in

Data may be transmitted in the eigenmode. Transmitting data in eigenmode typically provides better performance than simply transmitting data from T transmit antennas without any spatial processing. The receiving station

To receive data transmissions sent to the eigenmode of

You can use the left singular vector in, or

The eigenvector at may be used. Table 1 shows the spatial processing performed by the transmitting station, the received symbols at the receiving station, and the spatial processing performed by the receiving station. In Table 1,

Should be sent

A T × 1 vector with up to data symbols.

Is a T × 1 vector with T transmit symbols transmitted from T transmit antennas.

Is

Obtained from the receiving antenna

R × 1 vector with a number of received symbols.

Is an R × 1 noise vector.

Is

T × 1 vector with up to detected data symbols, which is

Is the estimated value of the data symbol at.

  The eigenvalue decomposition and singular value decomposition of the complex matrix may be performed using an iterative process using Jacobi rotation. Jacobi rotation is also commonly referred to as Jacobi method and Jacobi transformation. Jacobi rotation eliminates off-diagonal elements of the complex matrix by performing a planar rotation on the matrix. In the case of a 2 × 2 complex Hermitian matrix, only one iteration of Jacobi rotation is necessary to obtain two eigenvectors and two eigenvalues for this 2 × 2 matrix. For larger complex matrices with dimensions greater than 2 × 2, the iterative process performs multiple iterations of Jacobi rotation to obtain the desired eigenvectors and eigenvalues for the larger complex matrix or to obtain singular vectors and singular values. obtain. As described below, each iteration of Jacobi rotation for a larger matrix uses eigenvectors of a 2 × 2 sub-matrix.

2x2 Hermite Matrix

The eigenvalue decomposition of may be performed as follows. Hermite Matrix

May be expressed as:

However, A, B, and D are arbitrary real values, and θ _b is an arbitrary phase.

The first step in eigenvalue decomposition is to apply a unitary transformation with two sides as follows:

However,

Is a symmetric real matrix with symmetric off-diagonal elements at locations (1,2) and (2,1) and containing real numbers.

Next, the target real number matrix

Is made a diagonal matrix using double-sided Jacobi rotation as follows:

However, the angle θ may be expressed as follows.

2 × 2 unitary matrix of eigenvectors

May be derived as follows.

The two eigenvalues λ1 and λ2 are based on equation (6) or as

May be derived based on

  In equation set (9), the ordering of the two eigenvalues is not fixed. λ1 may be larger or smaller than λ2. However, if the angle φ is constrained to be | 2φ | ≦ π / 2, then cos2φ ≧ 0 and sin2φ> 0 only if D> A. Thus, the ordering of the two eigenvalues may be determined by the relative magnitudes of A and D. If A> D, λ1 is a larger eigenvalue, and if D> A, λ2 is a larger eigenvalue. If A = D, sin2φ = 1 and λ2 is a larger eigenvalue.

If λ2 is a larger eigenvalue,

The two eigenvalues in may be swapped to maintain a predetermined ordering from the largest eigenvalue to the smallest eigenvalue,

The first and second columns may also be swapped correspondingly.

Maintaining this predetermined ordering for two eigenvectors in order from the largest eigenvalue to the smallest eigenvalue

Produces eigenvectors of larger sized matrices that are decomposed using. This is desirable.

Also, the two eigenvalues λ1 and λ2 are as follows:

May be calculated directly from the elements.

Equation (10) is

It is a solution of the characteristic equation. In equation (10), λ1 is obtained with a positive sign for the second quantity on the right hand side. λ2 is obtained with a minus sign for the second quantity. In this case, λ1 ≧ λ2.

Equation (8) is

It is necessary to calculate cosφ and sinφ in order to derive the elements. The calculation of cos φ and sin φ is complicated.

The elements of

May be calculated directly from the elements.

However, r1,1, r1,2 and r2,1 are

Where r is the size of r1,2. Since g1 is a complex value,

Contains the complex values in the second row.

The equation set (11) is

From

Is designed to reduce the amount of computation to derive For example, in equations (11c), (11d), and (11f), division by r is necessary. Instead, r is inverted to obtain r1. The equations (11c), (11d), and (11f) are multiplied by r1. This reduces the number of division operations. Division operations are computationally more expensive than multiplication. Also, instead of calculating the argument (phase) of the complex element r1,2 that requires an arctangent operation, and then calculating cosine and sine of this phase value to obtain c1 and s1, only square root operation is used. Various triangular identities are used to solve c1 and s1 as a function of the real and imaginary parts of r1,2. Furthermore, instead of calculating the arc tangent in equation (7) and the sine and cosine functions in equation (8),

Other trigonometric identities are used to solve for c and s as a function of

The equation set (11) is

To get

Perform complex Jacobi rotation on. The set of calculations in equation set (11) is

Is designed to reduce the number of multiplication, square root, and inversion operations required to derive. this is,

The computational complexity can be greatly reduced for the decomposition of larger sized matrices using.

The eigenvalues of may be calculated as follows:

1. Eigenvalue Decomposition Eigenvalue decomposition of an N × N Hermitian matrix greater than 2 × 2 as shown in equation (2) may be performed using an iterative process. This iterative process uses Jacobi rotation repeatedly to eliminate off-diagonal elements in an N × N Hermitian matrix. For the iterative process, an N × N unitary transformation matrix is formed based on the 2 × 2 Hermitian submatrix of the N × N Hermitian matrix and applied repeatedly to make the N × N Hermitian matrix diagonal. The Each unitary transformation matrix includes four non-trivial elements (ie, elements other than 0 or 1) derived from the elements of the corresponding 2 × 2 Hermitian submatrix. The transformation matrix is also called a Jacobi rotation matrix. After completing all Jacobi rotations, the resulting diagonal matrix contains the real eigenvalues of the N × N Hermitian matrix, and all the product of the unitary transformation matrices are the eigenvalues for the N × N Hermitian matrix. It is an N × N matrix.

In the following description, the index i indicates the number of iterations and is initialized as i = 0.

Is an N × N Hermitian matrix to be decomposed. However, N> 2. N × N matrix

Is

Diagonal matrix of eigenvalues of

Is an approximation of

As initialized. N × N matrix

Is

Matrix of eigenvectors of

Is an approximation of

As initialized.

Matrix

A single iteration of Jacobi rotation may be performed as follows: First, the current as follows

2 × 2 Hermitian matrix based on

Is formed.

Where dp, q is

Element at location (p, q) in

It is.

Is

2 × 2 sub-matrix,

The four elements of

Are the four elements at location (p, p), (p, q), (q, p) and) (q, q).

For example, as shown in equation set (11):

Eigenvalue decomposition of

2 × 2 unitary matrix of eigenvectors

Get.

For the eigenvalue decomposition of, the equation (4)

Is

And from equation (11)

Is

Supplied as

Next, the matrix

N × N complex Jacobi rotation matrix using

Is executed.

Respectively

(1, 1), (1, 2), (2, 1), (2, 2) exchanged locations (p, p), (p, q), (q, p), (q, It is a unit matrix having the four elements in q).

Has the following form:

However, v1,1, v1,2, v2,1 and v2,2 are

These four elements.

All other off-diagonal elements of are zero. Equation (111) is

Indicates a complex matrix containing complex values for v2,1 and v2,2.

Is also called a transformation matrix that performs Jacobi rotation.

Then matrix

Is updated as follows:

Equation (15) is

Delete two off-diagonal elements dp, q and dq, p at locations (p, q) and (q, p) respectively. The calculation is

The values of other off-diagonal elements in may be changed.

Also matrix

Is updated as follows:

Is

All Jacobi rotation matrices used for

May be viewed as a cumulative transformation matrix including

Each iteration of Jacobi rotation is

Delete the two off-diagonal elements. Multiple iterations of Jacobi rotation are

May be performed on different values of the indices p and q to eliminate all off-diagonal elements. The indices p and q may be selected in a predetermined way by searching all possible values together.

A single sweep over all possible values for the indices p and q may be performed as follows. The index p may be incremented from 1 to N-1 in increments of 1. For each value of p, the index q may be advanced from P + 1 to N in increments of one. For each combination of different values of p and q

Jacobi rotation iterations may be performed to update.

At each iteration

Is the current value for p and q and its iteration

Formed on the basis of

As shown in equation set (11)

Is calculated against

As shown in equation (14)

Is calculated using

Is updated as shown in equation (15).

Is updated as shown in equation (16).

For a given combination of values for p and q,

Jacobi rotation to update

If the magnitude of the off-diagonal element at location (p, q) and (q, p) at <is below a predetermined threshold, it may be skipped.

The sweep is for all possible values of p and q

Is composed of N · (N−1) / 2 iterations of Jacobi rotation.

Each iteration of Jacobi rotation is

The two off-diagonal elements are deleted, but other elements that may have been previously deleted may be changed. The effect of searching the indices p and q together is

Is to reduce the size of all off-diagonal elements of

Is a diagonal matrix

Get closer to.

Collectively

Including the accumulation of all Jacobi rotation matrices that give Therefore

But

As you get closer to

Is

Get closer to.

Any number of sweeps may be performed to obtain an increasingly accurate approximation. Computer simulation

We showed that four sweeps would be sufficient to reduce the off-diagonal elements to a negligible level, and that for most applications, three sweeps would be sufficient. A predetermined number of sweeps (eg, three or four sweeps) may be performed. Or

After each sweep to determine if is sufficiently accurate

Non-diagonal elements may be checked. For example, total error (for example,

The power in all off-diagonal elements) may be calculated after each sweep, compared to the error threshold, and if the total error falls below the error threshold, the iterative process may end. Also, the iterative process may be terminated using other conditions or criteria.

Also, the values for indices p and q may be selected in a deterministic manner. As an example, for each iteration i,

Of the largest off-diagonal elements are identified and denoted as dp, q. Next, this maximum off-diagonal element dp, q and

Contains three other elements at location (p, p), (q, p), and (q, q) at

Jacobi rotation may be performed using. The iterative process may be performed until an end condition is encountered. The termination condition may be, for example, completion of a predetermined number of iterations, satisfaction of the error criteria described above, or other conditions or criteria.

When the iterative process ends, the final

Is

Is a good approximation of the final

Is

Is a good approximation.

The column of

As eigenvectors of

The orthogonal element of

As eigenvectors.

Final

The eigenvalues at are ordered from largest to smallest. Because for each iteration

This is because the eigenvectors in are ordered.

Final

The eigenvectors at

Are ordered based on their associated eigenvalues.

FIG. 1 shows an N × N Hermitian matrix using Jacobi rotation under the condition of N> 2

Fig. 5 shows an iterative process for performing eigenvalue decomposition of

Matrix

Is

And index i is initialized as i = 1 (block 110).

For iteration i, the values for indices p and q are determined in a predetermined way (eg by advancing all possible values for these indices) or deterministically (eg maximum off-diagonal) By selecting an index value for the element). Then the matrix at the location determined by the indices p and q

2 × 2 matrix using 4 elements

Is formed (block 114). Then, for example, as shown in equation set (11):

Eigenvalue decomposition of

2 × 2 matrix of eigenvectors

Is obtained (block 116). Next, as shown in equation (14), an N × N complex Jacobi rotation matrix

Is a matrix

(Block 118). Next, the matrix

As shown in equation (15)

(Block 120). Also matrix

As shown in equation (16)

(Block 122).

next,

A determination is made whether to terminate the eigenvalue decomposition of (block 124). Termination criteria may be based on the number of iterations or sweeps already performed, error criteria, etc. If the answer to block 124 is “No”, the index i is incremented (block 126) and the process returns to block 112 for the next iteration. Otherwise, if it ends, the matrix

Is a diagonal matrix

Provided as an approximation of the matrix

But

Matrix of eigenvectors of

(Block 1218).

For MIMO systems with multiple subbands (eg, a MIMO system using OFDM), multiple channel response matrices for different subbands

You may get Iterative process for each channel response matrix

May be executed against the matrix

Get. These matrices are

Diagonal matrix of each eigenvector of

And matrix

Is an approximate value.
A high degree of correlation typically exists between adjacent subbands in a MIMO channel. This correlation is for the subband of interest

May be effectively utilized by an iterative process to reduce the amount of computation to derive. For example, the iterative process may be performed for one subband at a time starting at one end of the system bandwidth and moving toward the other end of the system bandwidth. For each subband k excluding the first subband, the final solution obtained for the previous subband k−1

May be used as the initial solution for the current subband k. The initialization for each subband k is

May be given as Next, the iterative process for subband k until an exit condition is encountered

Works on the initial solution of.

Also, the concepts described above may be used with respect to time. For every time interval t, the final solution obtained for the previous time interval t-1

May be used as an initial solution for the current time interval t. The initialization for each time interval t is

May be given as in this case,

Is the channel response matrix for time interval t. Next, the iterative process for the time interval t until an end condition is encountered

Works on the initial solution of. This concept may also be used for both frequency and time. For each subband in each time interval, the final solution obtained for the previous subband and / or the final solution obtained for the previous time interval is determined for the current subband and time interval. It may be used as an initial solution.

2. Singular value decomposition Also, the iterative process can be any complex matrix greater than 2x2.

May be used for singular value decomposition of.

The singular value decomposition of

As given.

The following observations may be made regarding: First, the matrix

And matrix

Are both Hermitian matrices. Second,

Is a column of

The right singular vector of

Is the eigenvector of. Similarly,

Is a column of

The left singular vector of

Is the singular vector. Third

The nonzero eigenvalue of

Equal to the nonzero eigenvalue of

Is the square of the corresponding singular value.

2x2 matrix of complex values

May be expressed as:

However,

Is

Is a 2 × 1 vector with elements in the first column.

Is

Is a 2 × 1 vector with elements in the second column.

The right singular vector of is

And may be calculated using the eigenvalue decomposition described above in equation (11). 2x2 Hermitian matrix

Is

Defined as

The elements of

It may be calculated based on the elements of

Hermite Matrix

in the case of,

So r2,1 does not need to be calculated. Equation set (11)

Apply to matrix

You may get

Is

Contains the eigenvectors of

It is also the right singular vector.

The left singular vector is

And may be calculated using the eigenvalue decomposition described above in equation set (11). 2x2 Hermitian matrix

Is

Defined as

The elements of are as follows

It may be calculated based on the elements of

Equation set (11)

Apply to matrix

You may get

Is

Contains the eigenvectors of. This is also

It is also the left singular vector.

N × N Hermitian matrix

The iterative process described above for the eigenvalue decomposition of is any complex matrix greater than 2 × 2

May be used for singular value decomposition of.

Has dimensions R × T. Where R is the number of rows and T is the number of columns.

The iterative process for singular value decomposition (SVD) may be performed in several ways.

In the first SVD embodiment, the iterative process is:

The right singular vector at

Derive an approximation of the scaled left singular value at. In this embodiment, a T × T matrix

Is

Is an approximation of

As initialized. RxT matrix

Is

Is an approximation of

As initialized.

In the case of the first SVD embodiment, the matrix

A single iteration of Jacobi rotation may be performed as follows to update First 2x2 Hermite Matrix

Is current

Formed on the basis of

Is

Sub-matrix of

Contains four elements at locations (p, p), (p, q), (q, p) and (q, q) at.

The utility of may be calculated as follows.

However,

Is

Column p of

Is

Column q.

Is

Location in

Element. The indices p and q are

It seems to be. The values of the indices p and q may be selected in various ways as described below.

Next, eigenvalue decomposition, for example, as shown in equation set (11)

Is executed,

2 × 2 unitary matrix of eigenvectors

Get. For this eigenvalue decomposition,

Is

Replaced with

Is

Supplied as
Then matrix

T × T complex Jacobi rotation matrix using

Is formed.

Is

(1,1), (1,2), (2,1), (2,2) exchanged locations (p, p), (p, q), (q, p), (q , Q) is a unit matrix having four elements.

Has the form shown in equation (14).

Then matrix

Is updated as follows:

Matrix

Is also updated as follows:

The matrix is also updated as follows:
For the first SVD embodiment, explicitly

Without calculating, the iterative process is

Repeatedly remove non-diagonal elements of. The indices p and q may be swept by advancing p from 1 to T-1 and by advancing q from P + 1 to T for each value of p. Or

The values of p and q for which is the maximum may be selected for each iteration. The iterative process is performed until an end condition is encountered. The termination condition may be a predetermined number of sweeps, a predetermined number of iterations, satisfaction of error criteria, etc.

When the iterative process ends, the final

Is

Is a good approximation of the final

Is

Is a good approximation. When it converges

It is. However, “T” indicates transposition. For a square diagonal matrix:

Is the final solution

May be given as For non-square diagonal matrices:

The nonzero diagonal element of

Is given by the square root of the diagonal elements of.

Is the final solution

As given.

FIG. 2 shows an arbitrary complex matrix larger than 2 × 2 using Jacobi rotation according to the second SVD embodiment.

2 shows an iterative process 200 that performs a singular value decomposition of. Matrix

Is

And index i is initialized as i = 1 (block 210).

For iteration i, the values of p and q are selected in a predetermined or deterministic manner (block 212). Then a 2x2 matrix

Is a matrix at locations determined by the indices p and q shown in equation set (20)

These four elements are used. Then, for example, as shown in equation set (11)

Eigenvalue decomposition of

2 × 2 matrix of eigenvectors

Is obtained (block 216). T × T complex Jacobi rotation matrix as shown in equation (14)

Is a matrix

(Block 218). Next, the matrix

As shown in equation (21)

(Block 220). Also, as shown in equation (22), the matrix

Is

(Block 222).

next,

A determination is made as to whether to terminate the singular value decomposition of (block 224). Termination criteria may be based on the number of iterations or sweeps that have already been performed, error criteria, etc. If the answer is “No” for block 224, index i is incremented (block 226) and the process returns to block 212 for the next iteration.

Otherwise, if you reach the end,

Post-processing is performed on

Is obtained (block 228).

Matrix

Is

Matrix of right singular vectors of

Supplied as an approximation of the matrix

Is

Matrix of left singular vectors

Supplied as an approximation of the matrix

Is

Matrix of singular values of

(Block 230).

The left singular value vector of the first SVD embodiment performs the scaled left singular vector

It may be obtained by obtaining a solution of and then normalizing.

The left singular vector of

May be obtained by performing an iterative process on the eigenvalue decomposition of.

In a second SVD embodiment, the iterative process is

The right singular vector at

The approximate value of the left singular vector at is directly derived. This SVD embodiment applies Jacobi rotation in a two-sided manner to obtain left and right singular vector solutions simultaneously. Arbitrary complex 2x2 matrix

Then the conjugate transpose of this matrix is

And in this case

Is

Two columns, and

It is also the complex conjugate of the row.

The left singular vector of

It is also the right singular vector.

The right singular vector of may be calculated using Jacobi rotation as described for equation set (18).

The left singular vector of can be obtained using Jacobi rotation as described for equation set (19).

May be obtained by calculating the right singular vector.

In the case of the second embodiment, a T × T matrix

Is

Is an approximation of

As initialized. R × R matrix

Is

Is an approximation of

As initialized. RxT matrix

Is

Is an approximation of

As initialized.

In the case of the second SVD embodiment, the matrix

A single iteration of Jacobi rotation to update may be performed as follows. First, current

2 × 2 Hermitian matrix based on

Is formed.

Is

2 × 2 sub-matrix,

Location (p1, P1), (P1, q1), (q1, p1), (q1, q1)
Contains four elements.

These four elements may be calculated as follows:

However,

Is

Column p1.

Is

Column q1.

Is

Location in

Element. Index p1 and q1 are

It seems to be. The indices p1 and q1 may be selected in various ways as described below.

For example, as shown in equation set (11):

Eigenvalue decomposition of

2 × 2 matrix of eigenvectors

Get. For this eigenvalue decomposition,

Is

Replaced with

Is

Supplied as Next, a T × T complex Jacobi rotation matrix

Is a matrix

And the locations (p1, p1), (p1, q1), (q1, p1)
, (Q1, q1)

The four elements are included.

Has the form shown in equation (14).

Another 2 × 2 Hermitian matrix

Also current

Formed on the basis of

Is

2 × 2 submatrix,

Location (p2, p2), (p2, q2), (q2, p2), (q2, q2)
Contains elements in.

The elements of may be calculated as follows:

However,

Is

Row p2.

Is

The line q2.

Is

Location in

Element.

The indices p2 and q2 are

It seems to be. The indices p2 and q2 may be selected in various ways as described below.

Then, for example, as shown in equation set (11):

Eigenvalue decomposition of

2 × 2 matrix of eigenvectors

Get. For this eigenvalue decomposition,

Is

Replaced with

Is

Supplied as Next, the matrix

R × R complex Jacobi rotation matrix using

At locations (p2, p2), (p2, q2), (q2, p2), (q2, q2)

The four elements are included.

Has the form shown in equation (14).

Then matrix

Is updated as follows:

Matrix

Is updated as follows:

Matrix

Is updated as follows:

In the case of the second embodiment, the iterative process is (1)

Jacobi rotation to eliminate off-diagonal elements using indices p1 and q1 in (2)

Using p2 and q2 in, Jacobi rotation for eliminating off-diagonal elements is obtained alternately. The indices p1 and q1 may be swept by advancing p1 from 1 to T-1 and by advancing q1 from p1 + 1 to T for each value of p1. Also, indexes p2 and q2 may be swept by advancing p2 from 1 to R-1, and by advancing q2 from p2 + 1 to R for each value of p2. Square matrix as an example

In this case, the index may be set as p1 = p2 and q1 = q2. Another example is a square or non-square matrix

, A set of p1 and q1 may be selected, then a set of p2 and q2 may be selected, then a new set of p1 and q1 may be selected, and a new set of p2 and q2 May be selected, and so on. Accordingly, new values are alternately selected for the indexes p1 and q1 and the indexes p2 and q2. Or for each iteration

The values of p1 and q1 where is the maximum may be selected,

The values of p2 and q2 that are the largest may be selected. The iterative process is performed until an exit condition is encountered, which may be a predetermined number of sweeps, a predetermined number of iterations, satisfaction of error criteria, etc.

When the iterative process ends, the final

Is

Is a good approximation of the final

Is

Is a good approximation of the final

Is

Is a good approximation. However,

Each

May be a rotated version of The above description does not fully constrain the left and right singular vector solutions, so the final

The diagonal elements of are positive real values. Final

The size of the element

It may be a complex value equal to the singular value of.

May not be rotated as follows.

However,

Is

Is a T × T diagonal matrix with diagonal elements having unit magnitudes and phases that are negative of the phase of the corresponding diagonal elements.

Each

Is the final approximate value.

FIG. 3 shows an arbitrary complex matrix larger than 2 × 2 using Jacobi rotation according to the second SVD embodiment.

FIG. 3 shows an iterative process 300 for performing a singular value decomposition of

Matrix

Is

And index i is initialized as i = 1 (block 310).

  For iteration i, the values for indices p1, q1, p2, and q2 are selected in a predetermined or deterministic manner (block 312).

2x2 matrix

Is a matrix at locations determined by the indices p1 and q1 shown in equation set (23)

(Block 314). next,

Eigenvalue decomposition of is performed, for example as shown in equation set (11),

2 × 2 matrix of eigenvectors

Is obtained (block 316). Next, a T × T complex Jacobi rotation matrix

Is a matrix

(Block 318). 2x2 matrix

Is a matrix at locations determined by indices p2 and q2, as shown in equation set (24)

(Block 324). Next, as shown in equation set (11):

Eigenvalue decomposition of

2 × 2 matrix of eigenvectors

Is obtained (block 326). Next, the R × R complex Jacobi rotation matrix

Is a matrix

(Block 328).

Next, the matrix

As shown in equation (25),

(Block 330).

Matrix

As shown in equation (26):

(Block 332).

Matrix

As shown in equation (27)

(Block 334).

next,

A determination is made whether to terminate the singular value decomposition of (block 336). The termination criteria may be based on the number of iterations or sweeps that have already been performed, error criteria, etc. If the answer to block 336 is “No”, the index i is incremented (block 338) and the process returns to block 312 for the next iteration. Otherwise, if you reach the end,

Post-processing is performed on

Is obtained (block 340). Matrix

Is

Supplied as an approximation of the matrix

Is

Supplied as an approximation of the matrix

Is

As an approximation of

For the first and second SVD embodiments, the final

The right singular vector at and the final

The left singular vectors at are ordered from the largest singular value to the smallest singular value. Because for each iteration (for the first SVD embodiment)

Singular vectors in (in the second embodiment)

This is because the singular vectors in are ordered.

For MIMO systems with multiple subbands, the iterative process is performed for each channel response matrix.

Executed against the matrix

Get. These are their

Matrix of right singular vectors for each

, Matrix of left singular vectors

Diagonal matrix of singular values

Is an approximate value. The iterative process may be performed for one subband at a time, starting from one end of the system bandwidth and moving toward the other end of the system bandwidth. For the first SVD embodiment, for each subband k except the first subband, the final solution obtained for the previous subband k−1.

May be used as the initial solution for the current subband k. Therefore

It is. For the second SVD embodiment, for each subband k except the first subband, the final solution obtained for the previous subband k−1.

May be used as an initial solution for the current subband k. Therefore

It is. For both embodiments, the iterative process operates on the initial solution for subband k until an end condition is encountered for the subband. This concept may be used for time or for frequency and time as described above.

  FIG. 4 shows a process 400 for decomposing a matrix using Jacobi rotation.

Multiple iterations of Jacobi rotation are performed on the first matrix of complex values using multiple Jacobi rotation matrices of complex values (block 412). The first matrix is the channel response matrix

,

Is

Correlation matrix, or other matrix.

The Jacobi rotation matrix is

And / or other matrices.

For each iteration, a submatrix may be formed based on the first matrix and may be decomposed to obtain eigenvectors for the submatrix. The Jacobi rotation vector may be formed using the eigenvectors and may be used to update the first matrix. A second matrix of complex values is derived based on the plurality of Jacobi rotation matrices (block 414). The second matrix includes orthogonal vectors;

Right singular vector of or

Matrix of eigenvectors of

It may be.

For the eigenvalue decomposition determined in block 416, a third matrix of eigenvalues

May be derived based on a plurality of Jacobi rotation matrices (block 420).

In the case of singular value decomposition according to the first embodiment or scheme, a third matrix of complex values

May be derived based on multiple Jacobi rotation matrices. Fourth matrix with orthogonal vectors

Is the third matrix

May be derived based on Singular value matrix

Is the third matrix

May be derived (block 422). In the case of singular value decomposition according to the second SVD embodiment, a third matrix with orthogonal vectors

And matrix of singular values

May be derived based on a plurality of Jacobi rotation matrices (block 424).

FIG. 5 shows an apparatus 500 for decomposing a matrix using Jacobi rotation. Apparatus 500 uses means for performing multiple iterations of Jacobi rotation on a first matrix of complex values using a plurality of Jacobi rotation matrices of complex values (block 512), and based on the plurality of Jacobi rotation matrices. And a second matrix of complex values

Includes means for deriving (block 514).

In the case of eigenvalue decomposition, apparatus 500 uses a third matrix of eigenvalues based on a plurality of Jacobi rotation matrices.

Further includes means for deriving (block 520). In the case of singular value decomposition based on the first SVD embodiment, the apparatus 500 uses a third matrix of complex values based on a plurality of Jacobi rotation matrices.

And a fourth matrix having orthogonal vectors based on the third matrix

And a matrix of singular values based on the third matrix

Is further included (block 522). In the case of singular value decomposition based on the second SVD embodiment, the apparatus 500 uses a third matrix with orthogonal vectors.

And a matrix of singular values based on multiple Jacobi rotation matrices

Further includes means for deriving (block 524).

3. System FIG. 6 shows a block diagram of an embodiment of an access point 610 and a user terminal 650 in a MIMO system 600. Access point 610 includes multiple (Nap) antennas that may be used for data transmission and reception. User terminal 650 includes multiple (Nut) antennas that may be used for data transmission and reception. For simplicity, the following description assumes that MIMO system 600 uses time division multiplexing (TDD) and a downlink channel response matrix for each subband k.

Uplink channel response matrix for that subband

The reciprocal of

Assume that

  On the downlink, at the access point 610, the transmit (TX) data processor 614 receives traffic data from the data source 612 and receives other data from the controller / processor 630. A TX data processor 614 formats, encodes, interleaves, and modulates the received data to generate data symbols. A data symbol is a modulation symbol for data. TX spatial processor 620 receives the data symbols and pilot symbols, multiplies the data symbols and pilot symbols, performs spatial processing using the eigenvectors or right singular vectors, if applicable, and transmits Nap stream transmission symbols as Nap. (TMTR) 622a to 622ap. Each transmitter 622 processes its transmit symbol stream and generates a downlink modulated signal. Nap downlink modulated signals from transmitters 622a through 622ap are transmitted from antennas 624a through 624ap, respectively.

  In the user terminal 650, Nut antennas 652a to 652ut receive the transmitted downlink modulated signals, and each antenna 652 supplies the received signal to a respective receiver (RCVR) 654. Each receiver 654 performs processing complementary to that performed by transmitter 622 and provides received symbols. A receive (RX) spatial processor 660 performs spatial matching filtering on the received symbols from all receivers 654a through 654ut and provides detected data symbols. The detected data symbol is an estimate of the data symbol transmitted by access point 610.

RX data processor 670 further processes (eg, symbol demaps, deinterleaves, and decodes) the detected data symbols and provides decoded data to data sink 672 and / or controller / processor 680.

[0096] A channel processor 678 processes the received pilot symbols and provides an estimate of the downlink channel response for each subband of interest,

Supply. Processors 678 and / or 680 may use each of the matrices using the techniques described herein.

Disassemble

You may get This is the downlink channel response matrix

For

Is an estimated value. Processors 678 and / or 680 can be configured as shown in Table 1,

Downlink spatial filter matrix for each subband of interest based on

May be derived. The processor 680 is

May be provided to RX spatial processor 660 for downlink matched filtering and / or

May be provided to TX spatial processor 690 for uplink spatial processing.

The processing for the uplink may be the same as or different from the processing for the downlink. Traffic data from data source 686 and other data from controller / processor 680 are processed by TX data processor 688 (eg, encoded, interleaved, modulated), multiplied with pilot symbols, and of further interest. For each subband

Is processed spatially by the TX spatial processor 690. Transmit symbols from TX spatial processor 690 are further processed by transmitters 654a through 654ut to generate Nut uplink modulated signals. These are transmitted via antennas 652a to 652ut.

  At access point 610, the uplink modulated signal is received by antennas 624a through 624ap and generates received symbols for uplink transmission. RX spatial processor 640 performs spatial matched filtering on the received data symbols and provides detected data symbols. RX data processor 642 further processes the detected data symbols and provides decoded data to data sink 644 and / or controller / processor 630.

Channel processor 628 processes the received pilot symbols and for the subbands of interest depending on how the uplink pilot is transmitted.

Supply an estimate of. Processors 628 and / or 630 may use each of the matrices using the techniques described herein.

Disassemble

Get. The processor 628 and / or 630 may also be

Uplink spatial filter matrix for each subband of interest based on

May be derived. The processor 680 is

May be provided to RX spatial processor 640 for uplink spatial matched filtering and / or

May be provided to TX processor 620 for downlink spatial processing.

  Controllers / processors 630 and 680 control the operation at access point 610 and user terminal 650, respectively. Memories 632 and 682 store data and program codes for access point 610 and user terminal 650, respectively. Processors 628, 630, 678, 680 and / or other processors may perform eigenvalue decomposition and / or singular value decomposition of the channel response matrix.

  The matrix decomposition techniques described herein may be implemented by various methods. For example, these techniques may be implemented in hardware, firmware, software, or a combination thereof. For hardware implementation, the processing units used for matrix decomposition are one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processors (DSPDs), programmable logic devices (PLDs). , Field programmable gate arrays (FPGAs), processors, controllers, microcontrollers, microprocessors, other electronic units designed to perform the functions described herein, or combinations thereof.

  For firmware and / or software implementations, matrix decomposition techniques may be implemented using modules (eg, procedures, functions, etc.) that perform the functions described herein. The software code may be stored in a memory (eg, memory 632 or 682 in FIG. 6) and executed by a processor (eg, processor 630 or 680). The memory unit may be implemented within the processor or external to the processor.

  Headings are included here for reference and to help locate certain sections. These headings are not intended to limit the scope of the concepts described under the headings. These concepts may have applicability to other sections throughout the specification.

  The above description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. . Accordingly, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

FIG. 1 shows a process for performing eigenvalue decomposition using Jacobi rotation. FIG. 2 shows a process for performing singular value decomposition using Jacobi rotation according to the first SVD embodiment. FIG. 3 shows a process for performing singular value decomposition using Jacobi rotation according to the second SVD embodiment. FIG. 4 shows the process of decomposing the matrix using Jacobi rotation. FIG. 5 shows an apparatus for decomposing a matrix using Jacobi rotation. FIG. 6 shows a block diagram of the access point and the user terminal.

Claims (45)

Performing multiple iterations of Jacobi rotation on a first matrix of complex values using multiple Jacobi rotation matrices of complex values;
At least one processor configured to derive a second matrix of complex values based on the plurality of Jacobi rotation matrices and including orthogonal vectors;
Memory connected to the at least one processor;
With a device. For each of the plurality of iterations, the at least one processor is:
Forming a sub-matrix based on the first matrix;
Decomposing the submatrix to obtain eigenvectors for the submatrix;
Forming a Jacobi rotation matrix using the eigenvectors;
The apparatus of claim 1, configured to update the first matrix using the Jacobi rotation matrix.   3. The apparatus of claim 2, wherein for each of the plurality of iterations, the at least one processor is configured to order eigenvectors for the submatrix based on eigenvalues for the submatrix.   The apparatus of claim 1, wherein the at least one processor is configured to derive a third matrix of eigenvalues based on the plurality of Jacobi rotation matrices. The at least one processor derives a third matrix of complex values based on the plurality of Jacobi rotation matrices;
The apparatus of claim 1, configured to derive a fourth matrix having orthogonal vectors based on the third matrix.   The apparatus of claim 5, wherein the at least one processor is configured to derive a matrix of singular values based on the third matrix.   The apparatus of claim 1, wherein the at least one processor is configured to derive a third matrix having orthogonal vectors based on the plurality of Jacobi rotation matrices.   The apparatus of claim 7, wherein the at least one processor is configured to derive a matrix of singular values based on the plurality of Jacobi rotation matrices.   The apparatus of claim 1, wherein the at least one processor is configured to select different values for a row index and a column index of a first matrix for multiple iterations of the Jacobi rotation.   For each of the plurality of iterations, the at least one processor identifies the largest off-diagonal element in the first matrix and performs the Jacobi rotation based on the largest off-diagonal element. The apparatus of claim 1, configured as follows.   The apparatus of claim 1, wherein the at least one processor is configured to terminate Jacobi rotation for the first matrix after a predetermined number of iterations.   The apparatus of claim 1, wherein the at least one processor is configured to determine whether an error criterion is satisfied and terminate the plurality of iterations of the Jacobi rotation when the error criterion is satisfied.   The apparatus of claim 1, wherein the first matrix has a dimension greater than 2 × 2. Performing multiple iterations of Jacobi rotation on a first matrix of complex values using multiple Jacobi rotation matrices of complex values;
Deriving a second matrix of complex values based on the plurality of Jacobi rotation matrices and including orthogonal vectors;
With a method.   Performing multiple iterations of Jacobi rotation on the first matrix includes forming a sub-matrix based on the first matrix for each iteration, and decomposing the sub-matrix to The method of claim 14, comprising: obtaining an eigenvector for a submatrix; forming a Jacobi rotation matrix using the eigenvector; and updating the first matrix using the Jacobi rotation matrix. Method. Deriving a third matrix of complex values based on the plurality of Jacobi rotation matrices;
Deriving a fourth matrix having orthogonal vectors based on the third matrix;
15. The method of claim 14, further comprising:   The method of claim 14, further comprising deriving a third matrix having orthogonal vectors based on the plurality of Jacobi rotation matrices. Means for performing a plurality of iterations of Jacobi rotation on a first matrix of complex values using a plurality of Jacobi rotation matrices of complex values;
Means for deriving a second matrix of complex values based on the plurality of Jacobi rotation matrices and including orthogonal vectors;
With a device. Means for performing a plurality of iterations of the Jacobi rotation on the first matrix;
For each iteration, means for forming a sub-matrix based on the first matrix;
Means for decomposing the submatrix to obtain eigenvectors for the submatrix;
Means for forming a Jacobi rotation matrix using the eigenvectors;
Means for updating the first matrix using the Jacobi rotation matrix;
The apparatus of claim 18 comprising: Means for deriving a third matrix of complex values based on the plurality of Jacobi rotation matrices;
Means for deriving a fourth matrix having orthogonal vectors based on the third matrix;
The apparatus of claim 18, further comprising:   The apparatus of claim 18, further comprising means for deriving a third matrix having orthogonal vectors based on the plurality of Jacobi rotation matrices. Initialize the first matrix into a unit matrix,
Initialize the second matrix into a complex-valued Hermitian matrix,
Form a complex-valued Jacobi rotation matrix for each iteration based on the second matrix, and update the first and second matrices for each iteration based on the Jacobi rotation matrix for the iteration To perform a plurality of iterations of Jacobi rotation on the second matrix,
Supplying the first matrix as a matrix of eigenvectors;
At least one processor configured to provide the second matrix as a matrix of eigenvalues;
Memory connected to the at least one processor;
With a device. The at least one processor for each of the plurality of iterations is
Forming a sub-matrix based on the second matrix;
Decomposing the submatrix to obtain eigenvectors for the submatrix;
23. The apparatus of claim 22, configured to form the Jacobi rotation matrix using eigenvectors for the sub-matrix. Means for initializing the first matrix into a unit matrix;
Means for initializing the second matrix into a complex-valued Hermitian matrix;
Means for forming a complex-valued Jacobi rotation matrix for each iteration based on the second matrix; and the first and second matrices for each iteration based on the Jacobi rotation matrix for the iteration. Means for performing a plurality of iterations of Jacobi rotation on said second matrix comprising means for updating;
Means for providing the first matrix as a matrix of eigenvectors;
Means for providing the second matrix as a matrix of eigenvalues;
With a device. Means for forming a complex-valued Jacobi rotation matrix for each iteration;
Means for forming a sub-matrix based on the second matrix;
Means for decomposing the submatrix to obtain eigenvectors for the submatrix;
Means for forming the Jacobi rotation matrix using eigenvectors of the sub-matrix;
25. The apparatus of claim 24, comprising: Initialize the first matrix into a unit matrix,
Initialize the second matrix to a matrix of complex values,
Forming a Jacobi rotation matrix for each iteration based on the second matrix;
Performing multiple iterations of Jacobi rotation on the second matrix by updating the first and second matrices for each iteration based on the Jacobi rotation matrix for the iterations;
At least one processor configured to provide the first matrix as a matrix of right singular vectors;
Memory connected to the at least one processor;
With a device. For each of the plurality of iterations, the at least one processor is:
Forming a sub-matrix based on the second matrix;
Decomposing the submatrix to obtain eigenvectors for the submatrix;
27. The apparatus of claim 26, configured to form the Jacobi rotation matrix using the eigenvectors.   27. The apparatus of claim 26, wherein the at least one processor is configured to derive a matrix of singular values based on the second matrix.   27. The apparatus of claim 26, wherein the at least one processor is configured to derive a matrix of left singular vectors based on the second matrix. Means for initializing the first matrix into a unit matrix;
Means for initializing the second matrix into a matrix of complex values;
Means for forming a Jacobi rotation matrix for each iteration based on the second matrix; and means for updating the first and second matrices for each iteration based on the Jacobi rotation matrix for the iteration. Means for performing a plurality of iterations of Jacobi rotation on the second matrix comprising:
Means for supplying the first matrix as a right singular vector;
With a device. Means for forming a Jacobi rotation matrix for each iteration;
Means for forming a sub-matrix based on the second matrix;
Means for decomposing the submatrix to obtain eigenvectors for the submatrix;
Means for forming the Jacobi rotation matrix using the eigenvectors;
32. The apparatus of claim 30, comprising: Initialize the first matrix into a unit matrix,
Initialize the second matrix into a unit matrix,
Initialize the third matrix to a matrix of complex values,
For each iteration, a first Jacobi rotation matrix is formed based on a third matrix, a second Jacobi rotation matrix is formed based on a third matrix, and the first Jacobi rotation matrix is Updating the first matrix, updating the second matrix based on the second Jacobi rotation matrix, and updating the third matrix based on the first and second Jacobi rotation matrices Performing multiple iterations of Jacobi rotation on the third matrix;
At least one processor configured to provide the second matrix as a matrix of left singular vectors;
Memory connected to the at least one processor;
With a device. For each of the plurality of iterations, the at least one processor is:
Forming a first sub-matrix based on the third matrix;
Decomposing the first submatrix to obtain an eigenvector for the first submatrix;
35. The apparatus of claim 32, configured to form the first Jacobi rotation matrix using eigenvectors for the first sub-matrix. For each of the plurality of iterations, the at least one processor is:
Forming a second sub-matrix based on the third matrix;
Decomposing the second sub-matrix to obtain an eigenvector for the second sub-matrix;
34. The apparatus of claim 33, configured to form the second Jacobi rotation matrix using eigenvectors for the second sub-matrix.   35. The apparatus of claim 32, wherein the at least one processor is configured to derive a matrix of right singular vectors based on the first matrix.   33. The apparatus of claim 32, wherein the at least one processor is configured to derive a matrix of singular values based on the third matrix. Means for initializing the first matrix into a unit matrix;
Means for initializing the second matrix into a unit matrix;
Means for initializing the third matrix into a matrix of complex values;
For each iteration, means for forming a first Jacobi rotation matrix based on the third matrix, means for forming a second Jacobi rotation matrix based on the third matrix, and the first Means for updating the first matrix based on a Jacobi rotation matrix, means for updating the second matrix based on the second Jacobi rotation matrix, and the first based on the second Jacobi rotation matrix. Means for performing a plurality of iterations of Jacobi rotation on said third matrix comprising means for updating a matrix of three;
Means for providing the second matrix as a matrix of left singular vectors;
With a device. The means for forming the first Jacobi rotation matrix is:
Means for forming a first sub-matrix based on the third matrix;
Means for decomposing the first sub-matrix to obtain eigenvectors for the first sub-matrix;
Means for forming the first Jacobi rotation matrix using eigenvectors for the first sub-matrix;
38. The apparatus of claim 37, comprising: Means for forming the second Jacobi rotation matrix are:
Means for forming a second sub-matrix based on the third matrix;
Means for decomposing the second sub-matrix to obtain eigenvectors for the second sub-matrix;
Means for forming the second Jacobi rotation matrix using eigenvectors for the second sub-matrix;
40. The apparatus of claim 38, comprising: A first plurality of iterations of Jacobi rotation is performed on the first matrix of complex values to obtain a first unitary matrix having orthogonal vectors, and a second Jacobi rotation is performed on the second matrix of complex values. At least one processor configured to perform a plurality of iterations to obtain a second unitary matrix having orthogonal vectors, wherein the first unitary matrix is an initial for the second unitary matrix At least one processor used as a solution;
Memory connected to the at least one processor;
With a device.   The at least one processor is configured to perform a third plurality of iterations of the Jacobi rotation on a third matrix of complex values to obtain a third unitary matrix having orthogonal vectors; 41. The apparatus of claim 40, wherein a unitary matrix of is used as an initial solution for the third unitary matrix.   41. The apparatus of claim 40, wherein the first and second matrices of complex values are channel response matrices for two frequency subbands.   41. The apparatus of claim 40, wherein the first and second matrices of complex values are two time interval channel response matrices. Means for performing a first plurality of iterations of Jacobi rotation on a first matrix of complex values to obtain a first unitary matrix having orthogonal vectors;
Means for performing a second plurality of iterations of Jacobi rotation on a second matrix of complex values to obtain a second unitary matrix having orthogonal vectors;
And wherein the first unitary matrix is used as an initial solution for the second unitary matrix.   45. The apparatus of claim 44, wherein the first and second matrices of complex values are channel response matrices for two frequency subbands.

Images