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
Hhd
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-max{ij}
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
Hhd=
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
aopt=-RHrd
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-1r1r0r1...⋮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
{Eyn+∑k=1M
a
k
yn-k2}=min
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
{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+2r1r2r3...rM
a
1
a
2
a
3
⋮
a
M
+
a
1
a
2
a
3
...
a
M
r0r1r2...rM-1r1r0r1...⋮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)
∂∂aε2=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
Adaptive Filters
The DFT, FFT, and Practical Spectral Analysis