Linear Prediction
1.1
2005/03/14 23:12:26 US/Central
2005/04/24 16:12:27 GMT-5
Douglas
L.
Jones
dl-jones@uiuc.edu
Douglas
L.
Jones
dl-jones@uiuc.edu
Jeffrey
Silverman
jsilv@rice.edu
Kyle
Clarkson
kclarks@rice.edu
Recall that for the all-pole design problem, we had
the overdetermined set of linear equations:
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
d
-1
H
d
h
d
Let's look more closely at
H
d
H
d
R
.
r
i
j
is related to the correlation of
h
d
with itself:
r
i
j
k
0
N
i
j
h
d
k
h
d
k
i
j
Note also that:
H
d
h
d
r
d
1
r
d
2
r
d
3
⋮
r
d
M
where
r
d
i
n
0
N
i
h
d
n
h
d
n
i
so this takes the form
a
opt
R
r
d
, or
R
a
r
, where R
is
M
M
, a
is
M
1
, and r
is also
M
1
.
Except for the changing endpoints of the sum,
r
i
j
r
i
j
r
j
i
. If we tweak the problem slightly to make
r
i
j
r
i
j
, we get:
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
is Toeplitz (diagonal elements equal),
and a
can be solved for with
O
M
2
computations using Levinson's recursion.
Statistical Linear Prediction
Used very often for forecasting
(e.g. stock market).
Given a time-series
y
n
, assumed to be produced by an auto-regressive (AR)
(all-pole) system:
y
n
k
1
M
a
k
y
n
k
u
n
where
u
n
is a white Gaussian noise sequence which is
stationary and has zero mean.
To determine the model parameters
a
k
minimizing the variance of the prediction error, we
seek
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
The mean of
y
n
is zero.
ε
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
a
ε
2
2
r
2
R
a
Setting equal to zero yields:
R
a
r
These are called the Yule-Walker equations. In
practice, given samples of a sequence
y
n
, we estimate
r
n
as
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.