**
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.

Sun Feb 12 23:42:52 CST 1995