DIRECT AND INVERSE UNITARY EIGENPROBLEMS IN SIGNAL
PROCESSING: AN OVERVIEW
Department of Mathematical Sciences
Northern Illinois University
DeKalb, IL 60115 USA
Department of Mathematics
Naval Postgraduate School
Monterey, CA 93940 USA
Department of Mathematics and Computer Science
Kent State University
Kent, OH 44242 USA
KEYWORDS. Unitary Hessenberg matrices, Szego polynomials, frequency estimation, updating and downdating least-squares approximants, eigenvalue computations, inverse eigenvalue problem.
Let denote the set of unitary upper Hessenberg matrices of order n with nonnegative subdiagonal elements. These matrices bear many similarities with real symmetric tridiagonal matrices, both in terms of their structure, their underlying connections with orthogonal polynomials, and the existence of efficient algorithms for solving eigenroblems for these matrices. The Schur parameterization of provides the means for the development of efficient algorithms for finding eigenvalues and eigenvectors of these matrices. These algorithms include the QR algorithm for unitary Hessenberg matrices , an algorithm for solving the orthogonal eigenproblem using two half-size singular value decompositions , a divide-and-conquer method [10,5], an approach based on matrix pencils , and a unitary analog of the Sturm sequence method . Aspects of inverse eigenproblems for unitary Hessenberg matrices are considered in  and efficient algorithms for constructing a unitary Hessenberg matrix from spectral data are presented in [13,3].
Unitary Hessenberg matrices are fundamentally connected with Szego \ polynomials; i.e., with polynomials orthogonal with respect to a measure on the unit circle in the complex plane . In particular, the Schur parameters of a unitary Hessenberg matrix are the recurrence coefficients of the Szego \ polynomials determined by a discrete measure on the unit circle. Moreover, the monic Szego polynomial of degree k is the characteristic polynomial of the leading principal submatrix of . The zeros of the Szego polynomial of degree n, which are the eigenvalues of H, are the nodes of the discrete measure. Furthermore, the weights of the measure are proportional to the squared moduli of the first components of the normalized eigenvectors of H. Algorithms for eigenproblems and inverse eigenproblems for unitary Hessenberg matrices are therefore useful in several computational problems in signal processing involving Szego polynomials.
Eigenproblems for unitary Hessenberg matrices naturally arise in several frequency estimation procedures in signal processing, including Pisarenko's method  and the composite sinusoidal modeling method .
In , an efficient and reliable algorithm is presented for discrete least-squares approximation on the unit circle by algebraic polynomials. This algorithms also applies to the special case of discrete least-squares approximation of a real-valued function given at arbitrary distinct nodes in by trigonometric polynomials. The algorithm is based on the solution of an inverse eigenproblem for unitary Hessenberg matrices presented in . This algorithm is an updating procedure in that the least-squares approximant is obtained by incorporating the nodes of the inner product one at a time. Numerical experiments show that the algorithm produces consistently accurate results that are often better than those obtained by general QR decomposition methods for the least-squares problem.
In  an algorithm is presented for downdating the Szego polynomials and given least-squares approximant when a node is deleted from the inner product. This scheme uses the unitary Hessenberg QR algorithm  with the node to be deleted as a shift. This algorithm can be combined with the fast Fourier transform (FFT) when the given nodes are a subset of equispaced points. This situation arises, for example, when an FFT is performed on a data set with some missing or spurious values. Moreover, the updating and downdating procedures, based on solving inverse eigenvalue problems and eigenvalue problems, can be combined to yield a sliding window scheme, in which one node is replaced by another.