Levinson–Durbin algorithm

Levinson–Durbin algorithm. The Levinson–Durbin algorithm is a recursive procedure used primarily in signal processing and time series analysis for efficiently solving the Yule–Walker equations. These equations arise when fitting an autoregressive model to a given set of autocorrelation coefficients. The algorithm provides a computationally efficient method for calculating the coefficients of a linear predictor and is foundational in areas like speech coding and spectral estimation.

Definition and purpose

The primary purpose of the Levinson–Durbin algorithm is to solve the Toeplitz system of linear equations that characterizes the Yule–Walker equations. This system emerges directly from the application of the Wiener–Khinchin theorem to the problem of linear prediction in stationary stochastic processes. The algorithm recursively computes the coefficients for an autoregressive model of increasing order, which is essential for minimizing the mean squared error in prediction. Its development was a significant advancement over direct matrix inversion methods like Gaussian elimination, offering substantial savings in computational resources. The procedure is named for its independent developers, mathematician Norman Levinson and statistician James Durbin.

Mathematical formulation

The mathematical problem involves a symmetric Toeplitz matrix $R$ constructed from the autocorrelation function values $r\_0,\; r\_1,\; \backslash dots,\; r\_p$. The Yule–Walker equations for an order-$p$ autoregressive model are given by $R\; a\; =\; r$, where $a$ is the vector of AR model coefficients and $r$ is a vector of autocorrelations. The algorithm leverages the recursive structure between solutions of order $m$ and $m+1$. A key intermediate quantity is the reflection coefficient (or partial autocorrelation), denoted $\backslash kappa\_m$, which is updated at each step. The recursion also updates the forward prediction error variance, a concept related to Burg's method.

Algorithm steps

The algorithm initializes with the zero-order solution, setting the error variance equal to the autocorrelation at lag zero. For each iteration increasing the model order, it computes a reflection coefficient using the dot product of the current coefficient vector and a reversed segment of the autocorrelation sequence. This coefficient is then used to update the coefficient vector for the new order through a specific recurrence relation, a process reminiscent of updates in the Schur algorithm. The procedure continues until the desired model order is reached, with each step also updating the error variance. The recursion ensures that all intermediate solutions, from order 1 to order $p$, are generated, which is useful for model order selection criteria like the Akaike information criterion.

Applications

A principal application is in linear predictive coding, a cornerstone technique in speech synthesis and the GSM standard for mobile telephony. It is used extensively in spectral density estimation to produce autoregressive spectral estimation, which provides higher resolution than traditional periodogram methods. The algorithm is also employed in geophysical signal processing for tasks like seismic data analysis and in adaptive filter theory for real-time signal prediction. Furthermore, it finds use in system identification for estimating parameters of linear systems and in the design of digital filters.

Computational complexity

The Levinson–Durbin algorithm reduces the computational complexity of solving the Yule–Walker equations from $O(n^3)$, typical of general linear system solvers like those from the LINPACK library, to $O(n^2)$. This quadratic time complexity is achieved by exploiting the symmetry and Toeplitz structure of the autocorrelation matrix, avoiding explicit matrix inversion. The space complexity is linear, $O(n)$, as it only requires storage for the autocorrelation sequence and the evolving coefficient vectors. This efficiency was historically critical for real-time applications on limited hardware, such as early digital signal processors.

Related algorithms

Several important algorithms are directly related or derived from the Levinson–Durbin procedure. The Burg's method provides an alternative for estimating reflection coefficients directly from the data, rather than from the autocorrelation sequence. The Schur algorithm offers a numerically stable alternative, often implemented in parallel hardware architectures. For non-Toeplitz systems, the Levinson recursion was generalized by the work of William Trench. Other related methods include the Berlekamp–Massey algorithm used in coding theory and the split Levinson algorithm, which reduces the number of multiplications required.