Recall that for the all-pole design problem, we had
the overdetermined set of linear equations:
(
h
d
00...0
h
d
1
h
d
0...0
⋮⋮⋱⋮
h
d
N−1
h
d
N−2...
h
d
N−M
)
a
1
a
2
⋮
a
M
≃−
h
d
1
h
d
2⋮
h
d
N
h
d
0
0
...
0
h
d
1
h
d
0
...
0
⋮
⋮
⋱
⋮
h
d
N
1
h
d
N
2
...
h
d
N
M
a
1
a
2
⋮
a
M
h
d
1
h
d
2
⋮
h
d
N
with solution
a=
H
d
H
H
d
-1
H
d
H
h
d
a
H
d
H
d
-1
H
d
h
d
Let's look more closely at
H
d
H
H
d
=R
H
d
H
d
R
.
r
i
j
r
i
j
is related to the correlation of
h
d
h
d
with itself:
r
i
j
=∑
k
=0N−maxij
h
d
k
h
d
k+|i−j|
r
i
j
k
0
N
i
j
h
d
k
h
d
k
i
j
Note also that:
H
d
H
h
d
=
r
d
1
r
d
2
r
d
3⋮
r
d
M
H
d
h
d
r
d
1
r
d
2
r
d
3
⋮
r
d
M
where
r
d
i=∑
n
=0N−i
h
d
n
h
d
n+i
r
d
i
n
0
N
i
h
d
n
h
d
n
i
so this takes the form
a
opt
=−(RH
r
d
)
a
opt
R
r
d
, or
Ra=−r
R
a
r
, where R
R is
M×M
M
M
, a
a is
M×1
M
1
, and r
r is also
M×1
M
1
.
Except for the changing endpoints of the sum,
r
i
j
≃ri−j=rj−i
r
i
j
r
i
j
r
j
i
. If we tweak the problem slightly to make
r
i
j
=ri−j
r
i
j
r
i
j
, we get:
(
r0r1r2...rM−1
r1r0r1...⋮
r2r1r0...⋮
⋮⋮⋮⋱⋮
rM−1.........r0
)
a
1
a
2
a
3
⋮
a
M
=−r1r2r3⋮rM
r
0
r
1
r
2
...
r
M
1
r
1
r
0
r
1
...
⋮
r
2
r
1
r
0
...
⋮
⋮
⋮
⋮
⋱
⋮
r
M
1
...
...
...
r
0
a
1
a
2
a
3
⋮
a
M
r
1
r
2
r
3
⋮
r
M
The matrix R
R is Toeplitz (diagonal elements equal),
and a
a can be solved for with
OM2
O
M
2
computations using Levinson's recursion.
Used very often for forecasting
(e.g. stock market).
Given a time-series
yn
y
n
, assumed to be produced by an auto-regressive (AR)
(all-pole) system:
yn=−∑
k
=1M
a
k
yn−k+un
y
n
k
1
M
a
k
y
n
k
u
n
where
un
u
n
is a white Gaussian noise sequence which is
stationary and has zero mean.
To determine the model parameters
a
k
a
k
minimizing the variance of the prediction error, we
seek
min
a
k
a
k
Eyn+∑
k
=1M
a
k
yn−k2=min
a
k
a
k
Ey2n+2∑
k
=1M
a
k
ynyn−k+∑
k
=1M
a
k
yn−k∑
l
=1M
a
l
yn−l=min
a
k
a
k
Ey2n+2∑
k
=1M
a
k
Eynyn−k+∑
k
=1M∑
l
=1M
a
k
a
l
Eyn−kyn−l
a
k
y
n
k
1
M
a
k
y
n
k
2
a
k
y
n
2
2
k
1
M
a
k
y
n
y
n
k
k
1
M
a
k
y
n
k
l
1
M
a
l
y
n
l
a
k
y
n
2
2
k
1
M
a
k
y
n
y
n
k
k
1
M
l
1
M
a
k
a
l
y
n
k
y
n
l
(1)
The mean of
yn
y
n
is zero.
ε2=r0+2(
r1r2r3...rM
)
a
1
a
2
a
3
⋮
a
M
+(
a
1
a
2
a
3
...
a
M
)(
r0r1r2...rM−1
r1r0r1...⋮
r2r1r0...⋮
⋮⋮⋮⋱⋮
rM−1.........r0
)
ε
2
r
0
2
r
1
r
2
r
3
...
r
M
a
1
a
2
a
3
⋮
a
M
a
1
a
2
a
3
...
a
M
r
0
r
1
r
2
...
r
M
1
r
1
r
0
r
1
...
⋮
r
2
r
1
r
0
...
⋮
⋮
⋮
⋮
⋱
⋮
r
M
1
...
...
...
r
0
(2)
∂ε2∂
a
=2r+2Ra
a
ε
2
2
r
2
R
a
(3)
Setting
Equation 3 equal to zero yields:
Ra=−r
R
a
r
These are called the
Yule-Walker equations. In
practice, given samples of a sequence
yn
y
n
, we estimate
rn
r
n
as
rn
^=1N∑
k
=0N−nynyn+k≃Eykyn+k
r
n
1
N
k
0
N
n
y
n
y
n
k
y
k
y
n
k
which is extremely similar to the deterministic least-squares
technique.
Prony's Method
Linear Predictive Coding in Voice Conversion
The DFT, FFT, and Practical Spectral Analysis