当前位置:首页 >> >> Direction-of-arrival estimation using the rank-revealing URV decomposition

Direction-of-arrival estimation using the rank-revealing URV decomposition

UMIACS-TR 91-46 CS-TR-2640

March 1991

Direction-of-Arrival Estimation Using the Rank-Revealing URV Decomposition
G. Adams M. F. Griffin G. W. Stewarty

abstract
An algorithm for updating the null space of a matrix is described. The algorithm is based on a new decomposition, called the URV decomposition, which can be updated in O(N ) and serves as an intermediary between the QR decomposition and the singular value decomposition. The URV decomposition is applied to a high-resolution direction of arrival problem based on the MUSIC algorithm. A virtue of the updating algorithm is the running estimate of rank.
2

United Technologies Research Center, East Hartford, CT 06108. G. Adams is currently with the School of Electrical Engineering, Cornell University, Ithica, NY 14853 yDepartment of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742. This work was supported in part by the Air Force O ce of Scienti c Research under Contract AFOSR-87-0188.

Direction-of-Arrival Estimation Using the Rank-Revealing URV Decomposition
G. Adams M. F. Griffin G. W. Stewart ABSTRACT

A algorithm for updating the null space of a matrix is described. The algorithm is based on a new decomposition, called the URV decomposition, which can be updated in O(N ) and serves as an intermediary between the QR decomposition and the singular value decomposition. The URV decomposition is applied to a high-resolution direction of arrival problem based on the MUSIC algorithm. A virtue of the updating algorithm is the running estimate of rank.
2

1. Introduction
Let Xm be a complex data matrix consisting of m data snapshot vectors xl from an N -element antenna array. An estimate of the autocovariance matrix at the H mth snapshot can be written Cm = XmXm or alternatively H ! Xm? ; H = (X Cm = Cm? + xmxm m? ; xm ) xH m
1 1 1

The eigenstructure approach to high resolution direction-of-arrival (DOA) estimation usually requires a spectral decomposition of Cm or a singular value decomposition (SVD) of Xm , from which the orthogonal (noise) subspace can be estimated and used in a line frequency estimation algorithm such as MUSIC. Since the ab initio calculation of any decomposition is expensive, it is desirable to calculate the orthogonal subspace of Xm from Xm? , a process called updating. Unfortunately, the SVD is di cult to update and all known SVD updating schemes require O(N ) operations for a m N matrix 1]. Because of this di culty, rank revealing QR decompositions 2] have received renewed interest. However, the QR decomposition does not provide an explicit basis for the orthogonal subspace. Recently, a new rank revealing decomposition, the URV decomposition (URVD) 3], has been developed. It can be updated in O(N ) time, and provides
1 3 2

1

2

DOA Estimation

a basis for orthogonal subspace. In this paper the URVD will be described along with some simulation results for the DOA estimation problem. Since the URVD has applications beyond DOA estimation, we will adopt a neutral notation and work with an n p matrix A. Owing to space limitations, we can give only a sketch of the decomposition and the updating algorithm. The reader is referred to 3] for details. Throughout this paper k k will denote the Frobenius norm de ned by X kAk = jaij j :
1 2 2

The smallest singular value of a matrix will be written as inf(A).

i;j

2. The URV Decomposition
Suppose that A has rank K . Then there are orthogonal matrices U and V such that ! R 0 V H; A=U 0 0

where R is an upper triangular matrix of order K . This decomposition is called the URV decomposition. Unlike the SVD, the URVD is not unique; in fact, the SVD is itself a URVD. However, we will be concerned with the case where R is fully triangular. Now suppose A is nearly of rank K in the sense that its singular values satisfy K > K p , where K is large compared to K . It can be shown that there is a rank revealing URVD of A of the form ! R F V H; A=U 0 G
1 +1 +1

where 1. R and G are upper triangular, 2. inf(R)=
2

K,
2

3. kF k + kGk =
1

K +1 +
2

p.
2

pub/reports/README

This report may be obtained by anonymous ftp from thales.cs.umd.edu. Get the le for further details.

DOA Estimation

3

3. De ation and Re nement
For a dynamic DOA problem it is expected that the number of sources, i.e., rank of the data matrix, or A, will change over time. An increase in rank usually makes itself felt in the usual way. On the other hand, a decrease in rank can hide itself in the matrix R of the URVD. Thus any updating algorithm must be able to detect rank degeneracy in R and act accordingly. An algorithm to compute a rank revealing URVD of a K K upper triangular matrix R is given next. The rst step is to determine if R is defective in rank. This problem can be solved by means of a condition estimator 4], which produce in O(K ) time a vector w of norm one such that
2

kRwk = inf(R):
The next step uses plane rotations 5] to reduce all but the last component of H w to zero. Speci cally, we determine a sequence V H ; V H ; : : :; VK? , of rotations that eliminate the rst K ? 1 component of w, so that w is zero except for one H H in its last component. Let QH = VK? VK? V H denote the product of the rotations. Next determine an orthogonal matrix P such that P H RQ is upper triangular. This may be done by applying V ; V ; : : : ; VK? from the right to R. The result of applying a rotation Vi to two columns of R is to place a nonzero element below the diagonal of R. A left rotation then eliminates this element and restores triangularity. The matrix P H is the product of the left rotations. Of course, to get a complete update of the decomposition the left and right rotations must be multiplied into U and V , respectively. However, for the DOA problem updating U is not needed, and therefore can be omitted. This entire process is O(K ). It can be shown that at this point the norm of the last column of R is bounded by the norm of w, so that R is in URV form. However, an additional re nement step will improve the estimate of the orthogonal subspace. The step consists of using rotations to reduce the rst p ? 1 elements of the last column to zero and then to reduce R back to triangular form. Again the rotations must be multiplied into U and V . The re nement takes O(K ) time.
1 2 1 1 2 1 1 2 1 2 2

4

DOA Estimation

4. Updating the URVD
In this section an algorithm is sketched to update a rank revealing URVD of A, when a row zH is appended to A; i.e., when A is replaced by ! A : (1) zH The updating procedure determines if the rank has either increased, decreased, or remained the same. To decide what is small, assume a user supplied tolerance, tol, and that q (2) = kF k + kGk tol. The rst step is to compute (xH yH ) = zH V , where x is of dimension K . The problem then becomes one of updating 1 0 R F ^ @ A = B 0 G C: A xH yH
def 2 2

There are two cases to consider. The rst, and simplest occurs when q + kyk tol. =
new 2 2 new

(3)

^ In this case A is reduced to triangular form by a sequence of rotations applied from the left. Since is less than or equal to the prescribed tolerance, the new URVD satis es (2), and the approximate rank does not increase. However, it is possible for the rank to decrease. Hence the rank is checked. If it has decreased, R is de ated as described in the last section. This step is O(p ). If (3) is not satis ed, there is a possibility that the rank has increased. Since the increase in rank can be at most one, the problem is to transform the matrix to upper triangular form without destroying all the small values in F and G. The rst step is to reduce yH so that it has only one nonzero component and G remains upper triangular. This is done by a sequence of rotation applied alternately from the right and the left | the right rotations to zero an element of yH and the left rotations to maintain the matrix in upper triangular form. Finally, the entire matrix is reduced to triangular form in the usual way. Then K is increased by one, and the new R is checked for degeneracy and if necessary reduced as described before. The result is the updated URVD.
2

DOA Estimation

5

5. Updating the DOA
Let us return to the problem of obtaining a high resolution DOA estimate by updating the covariance matrix Cm on a per snapshot basis. The signals consist of the standard M narrowband sources impinging on a uniform linear array composed of N (M < N ) identical, equally spaced, sensors. The narrowband signals with known angular frequency ! impinge on the array from directions, ; ; : : :; M . In the interest of space the reader is referred to 7] for additional details on the signal model and signal covariance matrix. As mentioned, we may obtain the estimate of the orthogonal subspace required for DOA estimation from the covariance matrix 6] or from the data matrix. In the later case, the problem becomes one of computing a DOA estimate from the updated data matrix H ! H ^m = Xm? ; (4) X xH m where < 1 is \forgetting factor." Comparing (4) with (1), we see that the problem of updating the orthogonal subspace is one of updating a URVD. Note that because < 1, the triangular factor of the URVD remains bounded as long as the signals remain bounded. Thus a tolerance can be chosen based on the size of the noise (for one such choice see 3]). The MUSIC algorithm was chosen here to illustrate a high resolution DOA estimator based on the URVD. Speci cally, for each data snapshot xm, the angular spectra is given by 1 Sm( ) = PN ; H l K je ( )vml j where eH ( ) = (1; e?j dsin = ; e?j dsin = ; : : :; e?j p? dsin = ) and vml is the lth column of the V matrix for the mth snapshot. The spacing between array sensors is d, and is the wavelength of the propagating wave. The angles i at which the function Sm ( ) peaks correspond to the DOA estimates. ^H The rst step is to update Xm using the procedure described in the last section. Since the matrix U is not needed for the MUSIC algorithm, it isn't necessary to update U in the rst step. After V and K are updated, Sm( ) is computed. These steps are repeated for each snapshot. Of course, and the tolerance must be chosen beforehand.
1 2 1 = +1 2 2 4 ( 1)2

6

DOA Estimation

6. Simulation Results
The data for the simulation consist of four uncorrelated sources impinging on a 10-element array from ?15o , 0o, 10o , and 20o . The forgetting factor was chosen to be 0.79, representing a 10 snapshot e ective window. The narrowband source frequency was set to 0.2 and =d = 2. Each of the four sources assumed an uniformly distributed random phase term from ? to . Moreover, white Gaussian noise, of variance = 1:0 and uncorrelated with the sources, was added to the data snapshots. Several experiments were conducted for various signal strengths, i.e., signal-to-noise ratio (SNR). The rst experiment is to see how well the rank is estimated for variation in tolerance, tol, and SNR. After several initial guesses for a choice of tol, we found that if tol is much less than 0:5 the rank is severely overestimated and sometimes exceeds the dimensions of the matrix. At tol=0.5, the instantaneous rank estimates were generally overestimated by 3-4. Starting with a 20 dB SNR and then dropping to -4 dB SNR, the rank estimate tends to decrease. As the tolerance increases to tol=1.0, the rank is still overestimated but now only by 1-2. The rank estimate improves considerably when tol=2.5. At tol=2.5, the rank estimate at 20 dB is perfect. As the SNR drops to -4 dB, the rank then toggles between 3 and 4. This drop in rank estimate is expected since the separation between subspaces becomes less clear as the SNR drops. For all cases, the convergence time of the estimates is about rank+1 snapshots. In Figure 1, an ensemble average of the rank estimate is shown where the estimate is an ensemble over 100 data sets. The results are for three di erent signal data sets for tol=2.5: 6 dB SNR, 0 dB SNR, and changing number of sources case. For the third data set, the initial four sources consisted of one at 12 dB SNR, and three at 0 dB SNR. At the 15 snapshot the number of sources decreased to two, one at 15o and the other at 5o. Both sources were at 6 dB SNR. At 6 dB SNR the average rank estimate is very stable and doesn't deviate much from the true rank. As the SNR drops to 0 dB, the rank estimate toggles between 3 and 4 and thus the average rank is shown to be 3.5. When the number of sources changes from four to two, the initial estimate increased by one as if detecting an additional source{note that one of the two sources is the same as one of the four sources. Then the rank estimate drops to 2.5. The instantaneous MUSIC eigenspectrum over a single data set is shown in Figure 2. The data was of four equal sources at 6 dB SNR. Here, 20-35 snapshots are superimposed over the true line angles. This can be compared to Figure 3, a
2

DOA Estimation

7

Figure 1. Ensemble Average of Rank for Three Cases.

Figure 2. URVD MUSIC DOA Estimate.

8

DOA Estimation

Figure 3. MUSIC DOA Estimate for 35 Snapshots. result of using MUSIC with a 35 snapshot covariance matrix. The next gure, Figure 4, illustrates the e ect when three of the sources are weak, 0 dB, and one source is strong, 12 dB. The estimation error is much greater now for the weak sources, since the algorithm is having trouble discerning what is noise and what is signal. The last gure, Figure 5, is the instantaneous rank estimate as a result of four coherent sources. The signal set is the same as before with a 6 dB SNR. Four coherent sources were simulated by removing the random phase component from the signal set. Since the e ective window is only 10 snapshots, the rank estimate is expected to degrade for fully coherent sources.

7. Summary
In this paper, a di erent two-sided orthogonal decomposition, the URVD, was described. A procedure was given to compute a rank revealing URVD in O(N ) time. Moreover, it was also shown how the rank revealing URVD factorization can be updated. The URVD was then applied to a DOA problem which is based upon updating the estimates of the autocovariance matrix. Simulation results of
2

DOA Estimation

9

Figure 4. URVD MUSIC For Di erent Signal Strengths.

Figure 5. Rank Estimate for 4 Coherent Sources.

10

DOA Estimation

the DOA problem were presented for several signal scenarios, including a coherent signal case.

References
1] J. R. Bunch and C. P. Nielson, \Updating The Singular Value Decomposition," Numerishce Mathematik, 31, pp. 111{129, 1978. 2] T. F. Chan, \Rank Revealing QR Factorizations," Linear Algebra and Its Applications, 88/89, pp. 67{82, 1987. 3] G. W. Stewart, \An Updating Algorithm For Subspace Tracking," University of Maryland Computer Science Technical Report CS-TR 2494, 1990. 4] N. J. Higham, \A Survey of Condition Number Estimation for Triangular Matrices," Siam Review, 29, pp. 575{596, 1987. 5] G. H. Golub and C. F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore Maryland, 1989. 6] R.D. DeGroat and R.A. Roberts, \E cient, Numerically Stabilized RankOne Eigenstructure Updating," IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-38,pp. 301-316, Feb. 1990. 7] S. Haykin, ed., Array Signal Processing, Prentice-Hall, Englewood Cli s, New Jersey, 1984.


更多相关文档:

...estimation using the rank-revealing URV decomposition.pdf

UMIACS-TR 91-46 CS-TR-2640 March 1991 Direction-of-Arrival Estimation Using the Rank-Revealing URV Decomposition G. Adams M. F. Griffin G. W. ...

DOWNDATING A RANK-REVEALING URV DECOMPOSITION.pdf

W. Stewart, Direction of arrival and the rank-revealing URV decomposition, in Procedings of ACASSP-91, Washington, DC, 1991, IEEE. 5] J. M. ...

On-line subspace estimation using a Schur-type method_图文_....pdf

Examples are the direction-of-arrival estimation problem, harmonic retrieval, ...Examples are the URV decomposition [ 11 and the rank revealing QR (RRQR)...

An updating algorithm for subspace tracking.pdf

\Direction-of-Arrival Estimation Using the Rank-Revealing URV Decomposition." In Proceedings of the IEEE International Conference on Acoustics, Speech and ...

On the issue of rank estimation in subspace tracking the NA-....pdf

direction of arrival (DOA) of narrowband plane-...Stewart's rank revealing URV 7] approximates the...Using an approximate decomposition in which (k) ...

ON-LINE SUBSPACE ESTIMATION USING A SCHUR-TYPE METH....pdf

URV decomposition [4, 5] and the Rank Revealing QR decomposition [6, 7]...of the Schur-based subspace estimation technique, we consider the direction ...

A Matrix Decomposition for On-line MIMO System Identification....pdf

The decomposition is a generalization of the URV decomposition and allows low...We have rank revealing decompositions of both H1 and H2, using a common ...

用MATLAB的时重要MATLAB tools.doc

Kalman Filter - filtering, smoothing and parameter estimation (using EM) for...UTVtools - computing and modifying rank-revealing URV and UTV decompositions ...

Joint DOD and DOA estimation for bistatic MIMO radar.pdf

arrivals (DOAs) and direction of departures (DODs...URV U ? [u1, y, uP], R ? diag([s1, y...full column rank, and the rank of them is P....

Subspace estimation using unitary Schur--type methods.pdf

Subspace estimation using unitary Schur--type methods_专业资料。Abstract--- ... like the rank revealing QRdecomposition [1], the URVdecomposition [9...

Projection Approximation Subspace Tracking.pdf

estimation plays an important role in a variety ...Recently rank revealing URV decomposition [23] and...soids or directions of arrival (DOA) of plane ...

...Algorithm for a Generalization of a URV Decomposition.pdf

a Generalization of a URV Decomposition_专业资料。...The literature on condition 2 estimation contains ... of a rank revealing matrix decomposition. ...

...methods for block generalized schur decompositions, tech_....pdf

7,9,13,20,21], and rank-revealing URV 25]... has taken a step further in this direction. ...us on using the CS decomposition theory; to L....

A block qr algorithm and the singular value decomposition_....pdf

A block qr algorithm and the singular value decomposition_专业资料。In this...nement step in updating rank-revealing URV and ULV decompositions 3, 2]. ...

Matlab的第三方工具箱大全(强烈推荐).doc

smoothing and parameter estimation (using EM) for linear dynamical systems ...rank-revealing URV and UTV decompositions Uvi_Wave - wavelet analysis varimax...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com