CoreSource checked

Levinson-Durbin Recursion

Solves Toeplitz linear systems from autocorrelation values using a stable recursive update.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Signal Processing
Difficulty: Intermediate
Family: Linear Prediction
Tier: Core
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Levinson-Durbin recursion computes linear prediction coefficients from autocorrelation terms by growing the solution order one step at a time. It reuses reflection coefficients to avoid a full matrix solve.

Core Concepts

toeplitz system solvinglinear predictionrecursionsignal processing

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use when the system matrix is Toeplitz and comes from an autocorrelation sequence.
Use when linear prediction coefficients are needed faster than a generic solver can provide.

When Not to Use

Avoid when the matrix is not Toeplitz or the autocorrelation estimate is unreliable.
Avoid when numerical conditioning is poor enough that a more robust solver is needed.

What It Does

Uses autocorrelation values from a stationary signal model
Computes reflection coefficients recursively
Builds linear prediction coefficients for increasing model orders

Use Cases

Linear predictive coding
Autoregressive signal modeling
Fast solves for Hermitian Toeplitz systems

Inputs

Autocorrelation sequence r[0..p] of a stationary time series
Prediction filter order p

Outputs

Linear predictor coefficients a[1..p] and reflection coefficients k[1..p]
Minimum mean-square prediction error variance E_p

Key Formulas (1)

Reflection coefficient

k_m = (r_m − sum_{j=1}^{m−1} a_j·r_{m−j}) / E_{m−1}

k_m = (r_m - sum_{j=1}^{m-1} a_j*r_{m-j}) / E_{m-1}

Updates autoregressive coefficients for a Toeplitz system.

Pseudocode

1.Initialize prediction error from r[0]
2.For each model order
3.Compute the reflection coefficient from autocorrelation and previous coefficients
4.Update coefficients symmetrically from the previous order
5.Update the prediction error
6.Return the final coefficients and error

Canonical Example

Input: autocorrelation r = [1.0, 0.5, 0.25] for order 2
Output: prediction coefficients and final error estimate
Explanation: Each recursion order uses the previous coefficients and error to compute the next reflection coefficient.

Implementation Notes

Keep the previous order's coefficients before updating the next order.
Track prediction error energy and stop if it becomes nonpositive.
Test against a small Toeplitz solve from a generic linear solver.

Common Pitfalls

Autocorrelation values that do not define a positive-definite system can destabilize the recursion.
Indexing prediction coefficients by order is easy to get wrong.
Ignoring reflection coefficient magnitude hides unstable prediction filters.