Matrix methods to speed processing for MVDR beamforming

Abstract

A numerically stable and computationally efficient method for updating and downdating during MVDR (minimum variance distortionless response) adaptive beamforming. The method involves downdating and updating of the triangular (Cholesky) factor of the covariance matrix. The covariance matrix is never explicitly formed, but rather is partitioned and expanded after substituting in the Cholesky factors.

Claims

1. A method of performing efficient downdating and updating calculations for a Minimum Variance Distortionless Response (MVDR) adaptive beamforming system having an array of antenna elements, comprising: calculating weights for the antenna elements, using an MVDR algorithm that calculates the weights based on a covariance matrix, input data values, and steering vector values; performing a Cholesky factorization of the covariance matrix; wherein the MVDR algorithm has a downdating term and an updating term, for downdating and updating the Cholesky factorization, respectively; combining upper and lower Cholesky factors of the covariance matrix with input data vectors and steering vectors during computation of the MVDR algorithm, thereby generating pre-whitened input data vectors and steering vectors, as an alternative to re-forming and inverting the covariance matrix; for downdating, subtracting the downdating term from a previous value of the Cholesky factorization; and for updating, adding the updating term to the difference between the Cholesky factorization and the downdating term; wherein a unitary matrix is formed to represent a downdating or updating transformation.

2. The method of claim 1, wherein the unitary matrix is a sequence of Householder reflections.

3. The method of claim 2, wherein the Householder reflections are performed iteratively upon Cholesky column vectors and input data vectors.

4. The method of claim 2, wherein the Householder reflections are stabilized hyperbolic Householder reflections based on geometric considerations of the reflection's mechanism.

5. The method of claim 1, wherein the unitary matrix is used to form augmented matrices.

6. The method of claim 5, wherein the augmented matrices are used to form a set of partitioned matrix equations.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) A more complete understanding of the present embodiments and advantages thereof may be acquired by referring to the following description taken in conjunction with the accompanying drawings, in which like reference numbers indicate like features, and wherein:

(2) FIG. 1 illustrates an antenna array configured to performed MVDR adaptive beamforming in accordance with the invention.

(3) FIG. 2 illustrates how updating and downdating are conventionally performed for the covariance matrix of an MDVR algorithm.

(4) FIG. 3 illustrates the adaptive beam output for the antenna array of FIG. 1.

(5) FIG. 4 illustrates the incorporation of Cholesky factors to produce a pre-whitened steering vector and pre-whitened signal data vector.

(6) FIG. 5 illustrates the Cholesky factor employed for the equation of FIG. 2.

(7) FIG. 6 illustrates a mathematical structure for a matrix containing the steering vectors.

(8) FIG. 7 illustrates a set of equations obtained from augmented matrices.

(9) FIG. 8 illustrates a unitary matrix for downdating and updating as a sequence of Householder reflections.

(10) FIG. 9 illustrates an augmented equation that is the basis of the downdating transformation.

(11) FIG. 10 illustrates a comparison of conventional MVDR calculations and calculations using the method of the invention.

DETAILED DESCRIPTION OF THE INVENTION

(12) The following description is directed to an improved method for performing MVDR calculations. The method is useful for any MVDR application, but is particularly useful for adaptive beamforming in nonstationary environments where fast calculations are most needed. The method provides high computational efficiency and reduced computation time as compared to conventional MVDR calculation methods.

(13) As indicated in FIG. 1, the method is implemented with an antenna array 11 having a number of antenna elements whose signals are processed adaptively. Each element of the adaptive antenna array is weighted. The weighted antennas are then summed at the beamformer's output such that the combined effect is a beam pattern pointing towards a desired direction for signal transmission or receiving.

(14) A processing unit 12 receives and delivers signal data vectors and weight vectors to the antenna elements and has appropriate hardware and software to perform the method described herein. The method calculates MVDR beamformer weights, which when applied to the antenna elements steer the response of the antenna array in a specific direction or set of directions.

(15) The MVDR algorithm first computes an optimal weight vector from an estimated covariance matrix and a steering array vector. The weight vector and signal data vector are then combined to give the beamformer's output. The steering array vector represents the direction of the desired signal. Mathematical expressions for the relationship between the weight outputs, covariance matrix, steering array vector, and input signal data array vector are known in the field of MVDR beamforming.

(16) To obtain the optimum weights of the array, an ideal MVDR beamformer would use an exact covariance matrix of the signal data. In practice, it is not feasible to calculate the exact covariance matrix so an estimate of the covariance matrix is used. In addition, as the signal environment changes, the weight vectors must be updated (adapted) to reflect varying conditions. This adaptive computation of covariance estimates results in a significant increase in the computational load of the array processor 12. The following method is directed to reducing the computational load.

(17) A feature of the invention is that a covariance matrix is never explicitly formed. As explained below, updating and downdating of new and old data is employed within the MDVR algorithm. The key is combining Cholesky factorization of the covariance matrix with the updating or downdating.

(18) To compute the beam outputs as new data arrives, the process of obtaining a new Cholesky factor is broken up into two steps. The first step is downdatingthe processing associated with the subtraction of a downdating term. The second step is updatingthe processing associated with the addition of an updating term.

(19) FIG. 2 represents how updating and downdating is conventionally performed for the covariance matrix, R. The first term on the right side of the equation is the old covariance matrix, the second term is the updating term, and the third term is the downdating term.

(20) FIG. 3 illustrates the adaptive beam output, where is the elevation, is the azimuth, (, ) is the array steering vector, and R is the estimated covariance matrix.

(21) The covariance matrix can be factored into Cholesky factors (or any other factors). The covariance matrix is replaced with its Cholesky factors. In accordance with the method, the upper and lower Cholesky factors of the covariance matrix are combined with the input data and steering vectors within the MVDR algorithm. This generates prewhitened data and steering vectors and are the only quantities needed to compute the beam outputs.

(22) With the MVDR algorithm described by prewhitened data and steering vectors, the problem is to determine the updated Cholesky factor based on the previous Cholesky factor and the downdating term. This is accomplished by the development of augmented matrices. Subsequently, the new algorithm shows that there is a unitary matrix representing the downdating transformation and similarly for updating. Further matrix manipulation allows for a development of matrices representing both downdating and updating procedures. From these matrix identities, a partitioning of them into a set of simultaneous equations is produced. From this, a matrix of prewhitened steering vectors as functions of azimuth and elevation is formed. This matrix is all that is needed to downdate. Similarly, another formed matrix of steering vectors is all that is needed to update.

(23) FIG. 4 illustrates the incorporation of the Cholesky factors to produce, .sub.k(,), representing the pre-whitened steering vector and, the pre-whitened data vector.

(24) Updating and downdating of the covariance matrix is a known method to obtain a new estimate of the matrix for every new snapshot of data across the antenna array. With downdating and updating of the snapshot data vector, the covariance matrix never needs to be explicitly formed. This implies then that the inverse covariance matrix of FIG. 3 need not be calculated directly. This reduces substantially the expensive computations needed to find the covariance matrix as found in conventional methodologies.

(25) FIG. 5 illustrates the Cholesky factor being employed upon FIG. 2 for the downdating step and putting the equation into matrix form.

(26) All of the pre-whitened steering vectors must be downdated and updated. A matrix of pre-whitened steering vectors must be formed.

(27) FIG. 6 illustrates the necessary structure for the matrix containing the steering vectors. This matrix is part of a set of partitioned matrices as explained below.

(28) FIG. 7 is a set of equations obtained from manipulated augmented matrices generated through the use of a downdating transformation using a unitary matrix, Q.sub.k. By forming the energy of these augmented matrices, A, this set of partitioned matrix equations is found as shown in FIG. 7. With these equations, the denominator of FIG. 4 can now be downdated.

(29) The updating of the FIG. 4 denominator is developed similarly with different augmented matrices to generate another set of partitioned matrix equations.

(30) A mechanism of the downdating and updating transformation is required in order for the overall algorithm to work. The determination of the transformation is required to complete the algorithm explained above. There are many ways to do this found in literature such as Givens rotations.

(31) For the embodiment of this invention, stabilized hyperbolic Householder reflections are used to perform the transformation. However, rather than perform brute force reflections on the covariance matrix, the Householder reflections were performed iteratively upon the appropriate Cholesky factor's column vectors and data vector.

(32) FIG. 9 illustrates an augmented equation that is the basis of the downdating transformation. L.sub.k is the lower triangular Cholesky factor of R.sub.k. X.sub.k-N has p columns of length n. The matrices W.sub.i are defined recursively by W.sub.i+1=H.sub.iw.sub.i.

(33) Each Householder reflection H.sub.i transforms the ith row and column of W.sub.1 into W.sub.n. After the last column is transformed, the result is FIG. 8.

(34) The transformation matrix for both downdating and updating is a sequence of Householder reflections as illustrated in FIG. 8. There are other transformations that can be used besides the Householder. In this case a modified version of the Householder is employed, the stabilized hyperbolic Householder transformation. The method is to consider the problem of determining the transformation matrix, Q.sub.k, such that FIG. 9 is operational for downdating and updating.

(35) Methods known in the art of the linear algebra of Householder reflections mechanism (or any other transformational matrix) with energy conservation concept may be used to determine the required set of equations necessary to implement downdating of the Householder reflections transformation (or any other transformation) based on a matrix's column-by-column operation. The mechanism for updating the transformation matrix is similar but producing a different set of computational equations.

(36) Referring again to FIG. 9, the augmented matrix equation has a mixture of known elements and unknown elements. By understanding the structure of the Cholesky factor, and the process by which the reflections are performed, a sequence of simple equations can be obtained as an algorithmic technique for updating. The method provides a significant decrease in computation time compared to conventional matrix methods used with the MVDR.

(37) For updating, the known and unknown elements are not mixed on the same side of the equation as for downdating. Consequently, a new set of unique equations reflect the updating/reflections of the MVDR over time as new data is collected from the antenna array.

(38) FIG. 10 illustrates a comparison of the conventional MVDR calculations (using back substitution) to the calculations of the method described herein. A tenfold decrease in the number of multiplies per second is noted for this method.