Fast order-recursive Hermitian Toeplitz eigenspace techniques for array processing

TR Number



Journal Title

Journal ISSN

Volume Title


Virginia Polytechnic Institute and State University


Eigenstructure based techniques have been studied extensively in the last decade to estimate the number and locations of incoming radiating sources using a passive sensor array. One of the early limitations was the computational load involved in arriving at the eigendecompositions. The introduction of VLSI circuits and parallel processors however, has reduced the cost of computation A tremendously. As a consequence, we study eigendecomposition algorithms with highly parallel and A localized data flow, in order to take advantage of VLSI capabilities.

This dissertation presents a fast Recursive/Iterative Toeplitz (Hermitian) Eigenspace (RITE) algorithm, and its extension to the generalized strongly regular eigendecomposition situation (C-RITE). Both procedures exhibit highly parallel structures, and their applicability to fast passive array processing is emphasized. The algorithms compute recursively in increasing order, the complete (generalized) eigendecompositions of the successive subproblems contained in the maximum size one. At each order, a number of independent, structurally identical, non-linear problems is solved in parallel. The (generalized) eigenvalues are found by quadratically convergent iterative search techniques. Two different search methods, a restricted Newton approach and a rational approximation based technique are considered. The eigenvectors are found by solving Toeplitz systems efficiently. The multiple minimum (generalized) eigenvalue case and the case of a cluster of small (generalized) eigenvalues are treated also. Eigenpair residual norms and orthonormality norms in comparison with IMSL library routines, indicate good performance and stability behavior for increasing dimensions for both the RITE and C-RITE algorithms.

Application of the procedures to the Direction Of Arrival (DOA) identification problem, using the MUSIC algorithm, is presented. The order-recursive properties of RITE and C-RITE permit estimation of angles for all intermediate orders imbedded in the original problem, facilitating the earliest possible estimation of the number and location of radiating sources. The detection algorithm based on RITE or C-RITE can then stop, thereby minimizing the overall computational load to that corresponding to the smallest order for which angle of arrival estimation is indicated to be reliable.

Some extensions of the RITE procedure to Hermitian (non-Toeplitz) matrices are presented. This corresponds in the array processing context to correlation matrices estimated from non-linear arrays or incoming signals with non-stationary characteristics. A first—order perturbation approach and two Subspace Iteration (SI) methods are investigated. The RITE decomposition of the Toeplitzsized (diagonally averaged) matrix is used as a starting point. Results show that the SI based techniques lead to good approximation of the eigen-information, with the rate of convergence depending upon the SNR ar1d the angle difference between incoming sources, the convergence being faster than starting the SI method from an arbitrary initial matrix.