DIRECT AND INVERSE UNITARY EIGENPROBLEMS IN SIGNAL
PROCESSING: AN OVERVIEW
G.S. Ammar
Department of Mathematical Sciences
Northern Illinois University
DeKalb, IL 60115 USA
ammar@math.niu.edu
W.B. Gragg
Department of Mathematics
Naval Postgraduate School
Monterey, CA 93940 USA
gragg@guinness.math.nps.navy.mil
L. Reichel
Department of Mathematics and Computer Science
Kent State University
Kent, OH 44242 USA
reichel@mcs.kent.edu
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 [9],
an algorithm for solving the orthogonal eigenproblem using two
half-size singular value decompositions [1], a
divide-and-conquer method [10,5], an approach based on matrix
pencils [6], and a unitary analog of the Sturm sequence method
[7]. Aspects of inverse eigenproblems for unitary Hessenberg
matrices are considered in
[3] 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 [8]. 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 [2] and the composite sinusoidal modeling method [11].
In [12], 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 [3]. 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 [4] 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 [9] 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.