next up previous
Next: Toeplitz Inversion Formulas Up: Classical Foundations of Algorithms Previous: Fast Cholesky factorization

The Szego Recursions and Levinson's Algorithm


Another class of Toeplitz solvers arises from Szego 's theory of polynomials that are orthogonal with respect to a measure on the unit circle in the complex plane. A bounded nondecreasing distribution function with more than n points of increase on defines a measure on the unit circle on the complex plane, and an inner product on the set of polynomials of degree at most n, according to


This inner product on is determined by its moments , . Note that

so that the moment depends only on the difference j-k. The moment matrix is therefore a Hermitian positive definite Toeplitz matrix. Conversely, it follows from the solution of the classical trigonometric moment problem that every positive definite Hermitian Toeplitz matrix arises as the first n+1 moments of an inner product on the unit circle in this manner. See, for example, [1,25].

The unique family of monic polynomials that satisfy


with is said to be orthogonal with respect to a measure on the unit circle. These orthogonal polynomials were studied by Szego [36] and are also known as the monic Szego polynomials associated with . Szego showed that these polynomials satisfy a simple recurrence relation, from which it follows that they can be generated using the following recursive procedure, which we refer to as the Szego recursions.


where denotes the polynomial obtained by conjugating and reversing the coefficients of in the monomial basis of .

The coefficients of the monic Szego polynomials provide a factorization of the inverse of the Toeplitz matrix. In particular, let denote the unit right triangular matrix of order n+1 whose kth column contains the coefficients of , with and for j>k, . Then in terms of matrices, the orthogonality condition (4.2) becomes


or equivalently,


where . Thus, the coefficients of the Szego polynomials determine the reverse Cholesky factorization of , and moreover, the Szego recursions provide an algorithm for constructing this factorization. This algorithm is known as the Levinson-Durbin algorithm. See, for example, [10,24].

The Cholesky factorization (3.1) and inverse Cholesky factorization (4.4) of M are related by , so that there is a close connection between Schur's algorithm and the Levinson-Durbin algorithm. In fact, when is defined from as in Proposition 3.1, then the Schur parameters generated by Schur's algorithm are equal to the recurrence coefficients generated during the Szego recursions. These parameters are often of interest in applications, where they are known as reflection coefficients or partial correlation coefficients.

This gives rise to the possibility of a hybrid algorithm, in which the Szego polynomials are generated by the Szego recursions, using recurrence coefficients generated by Schur's algorithm. Such an algorithm for computing Szego polynomials is proposed in [20] because of its advantages in parallel computing. Moreover, Schur's algorithm has better numerical behavior than Levinson's algorithm [21,11], so one can expect the hybrid approach to produce more accurate Szego polynomial coefficients than the Levinson-Durbin algorithm [21].

next up previous
Next: Toeplitz Inversion Formulas Up: Classical Foundations of Algorithms Previous: Fast Cholesky factorization

Greg Ammar
Thu Sep 18 20:40:30 CDT 1997