Parallel algorithms for group word problems
DAVID H. ROBINSON · 1993
This dissertation contains a study of the direction-finding algorithms commonly known by one of the following terms: signal (or noise) subspace algorithms, invariant subspace algorithms, or super-resolution algorithms. The algorithms derive their names from the fact that they are able to resolve the directions-of-arrival of sinusoidal signals impinging on an array of sensors--or equivalently, the frequencies of sinusoidal signals being sampled in time--by examining a basis of an invariant subspace of a covariance matrix formed from the signal samples, and the resolution of these algorithms is very much better than the Rayleigh resolution criterion, which was thought to be unbeatable for nearly a century. Two prominent algorithms of this type are the multiple signal classification (MUSIC) algorithm, and the estimation of signal parameters via rotational invariance techniques (ESPRIT) algorithm. The ESPRIT algorithm makes use of a basis for the range of a covariance matrix, and the MUSIC algorithm makes use of its orthogonal complement. All of the signal-subspace direction-finding algorithms make use of one of these two subspaces and so MUSIC and ESPRIT are presented in detail as examples of the class of algorithms. The sensitivity of signal-subspace algorithms is explored by using the gap metric as a means of measuring the distance between subspaces, and also by means of the small-sample Monte Carlo condition estimation method which was recently developed by Charles Kenney and Alan Laub. A new resolution criterion for direction-finding methods is given that is similar to the Rayleigh resolution criterion for the separation of sources of nearly equal spatial direction, or equivalently, of nearly equal frequency in the frequency estimation problem. Signal-subspace direction finding is applied to sensor arrays with focusing lenses. This problem is of particular importance to wide-band direction finding. Also, various methods of efficiently computing solutions to the signal-subspace problem are discussed.