Department of Mathematics, Naval Postgraduate School,
Stabilization of the UHQR Algorithm
Abstract
Pisarenko's method is a fundamental algorithm of statistical signal
processing and the spectral analysis of stationary time series. Its
first phase involves finding the noise subspace, the eigenspace
associated with the smallest eigenvalue(s) of a positive definite
Toeplitz matrix, in one formulation. This stimulates much recent
activity related with fast solution of Toeplitz systems of linear
equations. The key mathematical ideas here go back to Schur (1917).
The second phase, correctly formulated, involves computing eigenvalues,
and first elements of normalized eigenvectors, of unitary Hessenberg
(almost triangular) matrices. If this problem is formulated "as usual",
as an eigenproblem for a companion matrix, it can be arbitrarily badly
ill-conditioned. The problem in the correct formulation is well-
conditioned, with its input data coming directly from Schur's algorithm,
which is used for the first phase.
In 1986 we showed that, in principle, this problem could be solved by
the unitary Hessenberg QR (uhqr) algorithm, an O(n^2) process. There
is also an inverse algorithm (iuhqr) which allows addition of data.
Together, these two algorithms allow adaptive recursive least squares
polynomial fits of data defined on the unit circle in the complex plane
(trigonometic polynomials). These techniques have been "developed" in
a number of papers with Ammar and Reichel. There are also continuous
"Schur flows", analogous with "Jacobi flows" on real symmetric
tridiagonals (Deift). We shall not get into these pretty but very
academic questions here.
Our recent (1997!) stabilization of these algorithms is the main topic of
this talk. It involves a few cute tricks, like the ones every person who
does Scientific Computing should learn to do. Now we can handle problems
of (essentially) arbitrarily high orders. The mathematics of this whole
whole area is very beautiful. Our result shows that it can also be very
practical. We shall also present new results on the tqr (real symmetric
tridiagonal QR) algorithm, and discuss analogies between tqr and uhqr.
