THE FOLD / GRIND / THE-HOT-LOOP / THE LEVINSON-DURBIN
THE LEVINSON-DURBIN
a Toeplitz system solved by recursion
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Levinson–Durbin recursion solves a symmetric Toeplitz system — one whose diagonals are all constant — in O(n²) time instead of the O(n³) of general Gaussian elimination. It walks up in order, and at each step a single reflection coefficient extends the solution to one more dimension, reusing the structure the constant diagonals give. Applied to the autocorrelation of a signal (the Yule–Walker equations), it produces the coefficients of the best linear predictor — the heart of LPC speech coding, spectral estimation, and autoregressive modelling.
LIT verified live: over thousands of random positive-definite Toeplitz systems, the recursion’s solution satisfies T·a = −r to ~1e-15 and matches a direct Gaussian solve, with prediction error staying positive (window.__levinson). FIG no framing; the recursion and a direct solver both run in-browser.
LIT verified live: over thousands of random positive-definite Toeplitz systems, the recursion’s solution satisfies T·a = −r to ~1e-15 and matches a direct Gaussian solve, with prediction error staying positive (window.__levinson). FIG no framing; the recursion and a direct solver both run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-hot-loop — a tight order-by-order recurrence that never rebuilds the whole system, just adds one reflection at a time. AVAN (AI) built the instrument: the Levinson–Durbin recursion, a valid autocorrelation source, and a direct-solve cross-check.
Credit as content: Norman Levinson (1947), James Durbin (1960). The weave: David names the hot loop; I confirm the recursion solves the Toeplitz system exactly and matches the direct solve.
Credit as content: Norman Levinson (1947), James Durbin (1960). The weave: David names the hot loop; I confirm the recursion solves the Toeplitz system exactly and matches the direct solve.
3 ONE DIMENSION
A Toeplitz matrix: every diagonal is constant. The recursion climbs order by order, each step adding one reflection coefficient.
4 TWO DIMENSIONS · INTERACTIVE
A random autocorrelation defines a Toeplitz system; Levinson–Durbin’s coefficients match a direct solve, with residual near zero.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the predictor coefficients, built order by order.
AVAN’s addition (the inverse-companion): don’t invert the whole matrix — exploit the constant diagonals. The inverse of ‘solve T·a=−r by elimination’ is ‘each order adds one reflection coefficient, O(n²) total.’ Magenta is the O(n³) full solve; green is the recursion. Structure beats brute force.
LIT Genuine Levinson–Durbin recursion (Norman Levinson 1947, James Durbin 1960) for symmetric Toeplitz / Yule-Walker systems. Verified live: over 2000 random PD Toeplitz systems the O(n²) recursion gives T·a=−r residual under 1e-6 (max ~1.8e-15) and matches a direct Gaussian solve to ~3e-16, with prediction error E>0 (window.__levinson.residualOk, .matchesDirect).
FIG No framing: the recursion and a direct solver both run in-browser. The AVAN inverse is honest — rather than inverting the whole matrix, one exploits the constant diagonals: each order adds one reflection coefficient, O(n²) total. Magenta is the O(n³) full solve; green is the recursion. Structure beats brute force.
FIG No framing: the recursion and a direct solver both run in-browser. The AVAN inverse is honest — rather than inverting the whole matrix, one exploits the constant diagonals: each order adds one reflection coefficient, O(n²) total. Magenta is the O(n³) full solve; green is the recursion. Structure beats brute force.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-HOT-LOOP · David Lee Wise (ROOT0), with AVAN