ON THE LINEAR LEAST-SQUARE PREDICTION PROBLEM
R. M. Fern
´
andez-Alcal
´
a, J. Navarro-Moreno, J.C. Ruiz-Molina and M. D. Estudillo
Department of Statistic and Operations Research. University of Ja
´
en
Campus Las Lagunillas, s/n. 23071, Ja
´
en (Spain)
Keywords:
Correlated signal and noise, linear least-square prediction problems.
Abstract:
An efficient algorithm is derived for the recursive computation of the filtering and all types of linear least-
square prediction estimates (fixed-point, fixed-interval, and fixed-lead predictors) of a nonstationary signal
vector. It is assumed that the signal is observed in the presence of an additive white noise which can be
correlated with the signal. The methodology employed only requires that the covariance functions involved
are factorizable kernels and then it is applicable without the assumption that the signal verifies a state-space
model.
1 INTRODUCTION
The estimation of a signal in the presence of additive
white noise has been found to be among the central
problems of statistical communication theory.
Application of the linear least mean-square error
criterion leads to a linear integral equation, called
Wiener-Hopf equation, whose solution is the impulse
response of the optimal estimate. Although the lin-
ear least mean-square estimation problem is com-
pletely characterized by the solution to the Wiener-
Hopf equation, a great effort has been made in the
searching of efficient procedures for the computation
of the desired estimator. Roughly speaking two ap-
proaches have been applied.
A first via of solution consists in using integral-
equations approaches which provide the solution to
the Wiener-Hopf integral equation for the impulse re-
sponse function of the optimal estimator, from the
knowledge of the covariance functions of the sig-
nal and noise [see, e.g. (Van Trees, 1968), (Kailath
et al., 2000), (Fortmann and Anderson, 1973), (Gard-
ner, 1974), (Gardner, 1975), (Navarro-Moreno et al.,
2003)]. This technique is closely connected to series
representation for stochastic processes and, in gen-
eral, a series representation for the optimal estimate
is provided instead of a recursive computational algo-
rithm. The use of series representation for stochastic
processes only allow to derive recursive procedures
for the computation of suboptimum estimates.
On the other hand, a conventional approach to esti-
mate a signal observed through a linear mechanism
lies in imposing structural assumptions on the co-
variance functions involved. In this framework, the
most representative algorithm is the Kalman-Bucy fil-
ter [see. e.g., (Kalman and Bucy, 1961), (Gelb, 1989)]
which requires that the signal verifies a state-space
model. However, although the Kalman-Bucy filter
has been widely applied, there are a great number
of physical phenomena that cannot be modelled by a
state-space system. For problems with covariance in-
formation, linear least mean-square estimation algo-
rithms have been designed under less restrictive struc-
tural conditions on the processes involved [(Sugisaka,
1983), (Fern
´
andez-Alcal
´
a et al., 2005)]. Specifically,
the only hypothesis imposed is that the covariance
functions of the signal and noise are expressed in the
factorized functional form.
Therefore, under the assumption that the covari-
ance functions of the signal and noise are factoriz-
able kernels, we aim to derived a recursive solution
to the linear least-square estimation problem involv-
ing correlation between the signal and the observation
noise. Specifically, using covariance information, an
imbedding method is employed in order to design re-
cursive algorithms for the filter and all kinds of pre-
dictors (fixed-point, fixed-interval, and fixed-lead pre-
dictors). Moreover, recursive formulas are designed
for the error covariances associated with the above es-
timates.
332
M. Fernández-Alcalá R., Navarro-Moreno J., C. Ruiz-Molina J. and D. Estudillo M. (2005).
ON THE LINEAR LEAST-SQUARE PREDICTION PROBLEM.
In Proceedings of the Second International Conference on Informatics in Control, Automation and Robotics - Signal Processing, Systems Modeling and
Control, pages 332-335
DOI: 10.5220/0001160303320335
Copyright
c
SciTePress
Then, the paper is structured as follows. In the
next section, a general formulation of the linear least-
squares filtering and prediction problem is consid-
ered. Finally, in Section 3, the recursive algorithms
for the filter and all types of predictors as well as their
error covariances are derived.
2 PROBLEM STATEMENT
Let {x(t), 0 t < ∞} be a zero-mean signal vector
of dimension n which is observed through the follow-
ing equation:
y(t) = x(t) + v(t), 0 t <
where y(t) represents the n-dimensional observation
vector and v(t) is a centered white observation noise
with covariance function E[v(t)v
(s)] = r δ(t s),
with r a positive definite covariance matrix of dimen-
sion n × n, and correlated with the signal.
We assume that the autocovariance function of the
signal and the cross-covariance function between the
signal and the observation noise are factorizable ker-
nels which can be expressed in the following form:
R
x
(t, s) =
A(t)B
(s), 0 s t
B(t)A
(s), 0 t s
R
xv
(t, s) =
α(t)β
(s), 0 s t
γ(t)λ
(s), 0 t s
(1)
where A(t), B(t), α(t), β(t), γ(t), and λ(t) are
bounded matrices of dimensions n × k, n × k, n × l,
n × l, n × l
, and n × l
, respectively.
We consider the problem of finding the linear least
mean-square error estimator, ˆx(t/T ), with t T , of
the signal x(t) based on the observations {y(s), s
[0, T ]}. It is known that such an estimate is the or-
thogonal projection of x(t) onto H(y, t) (the Hilbert
space spanned by the process {y(s), s [0, T ]}).
Hence, ˆx(t/T ) can be expressed as a linear function
of all the observed data of the form
ˆx(t/T ) =
Z
T
0
h(t, s, T )y(s)ds, 0 s T t
(2)
As a consequence of the orthogonal projection the-
orem, we obtain that the impulse response function
h(t, s, T ) must satisfy the Wiener-Hopf equation
R
xy
(t, s) =
Z
T
0
h(t, σ, T )R(σ, s) + h(t, s, T )r
(3)
for 0 s T t, where R
xy
(t, s) = R
x
(t, s) +
R
xv
(t, s), and R(t, s) = R
x
(t, s) + R
xv
(t, s) +
R
vx
(t, s).
From (1), it is easy to check that R
xy
(t, s) and
R(t, s) can be written as follows:
R
xy
(t, s) =
F (t
(s), 0 s t
G(t
(s), 0 t s
R(t, s) =
Λ(t
(s), 0 s t
Γ(t
(s), 0 t s
(4)
where F (t) = [A(t), α(t), 0
n×l
], G(t) =
[B(t), 0
n×l
, γ(t)], Λ(t) = [A(t), α(t), λ(t)], and
Γ(t) = [B(t), β(t), γ(t)] are matrices of dimensions
n × m with m = k + l + l
, and 0
p×q
denotes the
(p × q)-dimensional matrix whose elements are zero.
Note that, we can expressed the optimal linear fil-
ter and all kinds of predictors through the equations
(2) and (3). Specifically, by considering T = t
we have the filtering estimate ˆx(t/t), the fixed-point
predictor ˆx(t
d
/T ) is derived by taking a fixed in-
stant t = t
d
> T , for the fixed-interval predictor,
we consider a fixed observation interval [0, T
d
], with
T
d
< t, and finally the fixed-lead prediction estimate
ˆx(T + d/T ), is given by (2) and (3) with t = T + d,
for any d > 0.
Likewise, the error covariances associated with the
above estimates can be defined as
P (t/T ) = E[(x(t) ˆx(t/T ))(x(t) ˆx(t/T ))
] (5)
with a suitable estimation instant, t, and a specific ob-
servation interval [0, T ].
Therefore, in the next section, the Wiener-Hopf
equation (3) will be used, with the aid of invariant
imbedding, in order to design recursive procedures for
the filter and all kinds of predictors of the signal vec-
tor x(t) as well as their associated error covariances.
We must note that the only hypothesis assumed is that
the covariance functions involved are factorizable ker-
nels of the form (1).
3 RECURSIVE LINEAR
ESTIMATION ALGORITHMS
Under the hypotheses established in Section 2, an ef-
ficient recursive algorithm for the linear least-square
filter, and the fixed-point, fixed-interval and fixed-lead
prediction estimates of the signal and their associated
error covariance functions is presented in the follow-
ing theorem.
Theorem 1 The filter and the fixed-point, fixed-
interval and fixed-lead prediction estimates of the sig-
nal x(t) are recursively computed as follows:
ˆx(t/t) =F (t)L(t)
ˆx(t
d
/T ) =F (t
d
)L(T )
ˆx(t/T
d
) =F (t)L(T
d
)
ˆx(T + d/T ) =F (T + d)L(T )
(6)
ON THE LINEAR LEAST-SQUARE PREDICTION PROBLEM
333
where the m-dimensional vector L(T ) obeys the dif-
ferential equation
T
L(T ) =J(T ) [y(T ) Λ(T )L(T )]
L(0) =0
m
(7)
with 0
m
the m-dimensional vector with zero elements,
and where J(T ) is given by the expression
J(T ) =
(T ) Q(T
(T )] r
1
(8)
with Q(T ) satisfying the differential equation
T
Q(T ) =J(T ) [Γ(T ) Λ(T )Q(T )]
Q(0) =0
m×m
(9)
Moreover, the optimal linear estimation error co-
variance functions associated with the filtering esti-
mate, P (t/t), the fixed-point predictor, P (t
d
/T ), the
fixed-interval predictor, P (t/T
d
), and the fixed-lead
predictor, P (T + d/T ), are formulated as follows:
P (t/t) =R
x
(t, t) F (t)Q(t)F
(t)
P (t
d
/T ) =R
x
(t
d
, t
d
) F (t
d
)Q(T )F
(t
d
)
P (t/T
d
) =R
x
(t, t) F (t)Q(T
d
)F
(t)
P (T + d/T ) =R
x
(T + d, T + d)
F (T + d)Q(T )F
(T + d)
(10)
proof 1 From (4), the Wiener-Hopf equation (3) can
be rewritten as
h(t, s, T )r = F (t
(s)
Z
T
0
h(t, σ, T )R(σ, s)
Now, we introduce an auxiliary function J(s, T )
satisfying the equation
J(s, T )r = Γ
(s)
Z
T
0
J(σ, T )R(σ, s) (11)
Then, it is obvious that the impulse response func-
tion is given by the expression
h(t, s, T ) = F (t)J(s, T ) (12)
Next, differentiating (11) with respect to T , we ob-
tain that J(s, T ) obeys the following partial differen-
tial equation:
T
J(s, T ) = J(T )Λ(T )J(s, T ) (13)
where J(T ) = J(T, T ).
On the other hand, from (4) and (11), it is easy to
check that
J(T )r = Γ
(T )
Z
T
0
J(σ, T )Γ(σ)Λ
(T )
Then, the definition of a function Q(T ) as
Q(T ) =
Z
T
0
J(σ, T )Γ(σ) (14)
leads to the equation (8).
The equation (9) is obtained by differentiating (14)
with respect to T and using (13) in the resultant equa-
tion.
Next, introducing a new auxiliary function
L(T ) =
Z
T
0
J(σ, T )y(σ) (15)
and substituting (12) in (2), we have that
ˆx(t/T ) = F (t)L(T ), t T (16)
Then, by considering a suitable estimation instant,
t, and a specific observation interval [0, T ] in (16),
the filter and all kinds of predictors are given by the
expressions (6).
Moreover, differentiating (15) with respect to T and
considering (13) in the resultant equation, it is easy to
check that the above function L(T ) satisfies the differ-
ential equation (7).
Finally, in order to derived the expressions (10) for
the error covariances associated with the above es-
timates, we remark that, from the orthogonal projec-
tion lemma, the error covariance function (5), can be
rewritten as
P (t/T ) = R
x
(t, t) E[ˆx(t/T )ˆx
(t/T )]
Then, substituting (16) in the above equation and
using (11), it is easy to check that
P (t/T ) = R
x
(t, t) F (t)Q(T )F
(t)
As consequence, the expressions given in (10) can
be obtained.
ACKNOWLEDGMENT
This work was supported in part by Project
MTM2004-04230 of the Plan Nacional de I+D+I,
Ministerio de Educaci
´
on y Ciencia, Spain. This
project is financed jointly by the FEDER.
REFERENCES
Fern
´
andez-Alcal
´
a, R. M., Navarro-Moreno, J., and Ruiz-
Molina, J. C. (2005). Linear Least-Square Estimation
Algorithms Involving Correlated Signal and Noise.
IEEE Trans. Signal Processing. Accepted for publi-
cation.
Fortmann, T. E. and Anderson, B. D. O. (1973). On the
Approximation of Optimal Realizable Linear Filters
Using a Karhunen-Lo
`
eve Expansion. IEEE Trans. In-
form. Theory, IT-19:561–564.
ICINCO 2005 - SIGNAL PROCESSING, SYSTEMS MODELING AND CONTROL
334
Gardner, W. A. (1974). A Simple Solution to Smoothing,
Filtering, and Prediction Problems Using Series Rep-
resentations. IEEE, Trans. Inform. Theory, IT-20:271–
274.
Gardner, W. A. (1975). A Series Solution to Smoothing,
Filtering, and Prediction Problems Involving Corre-
lated Signal and Noise. IEEE, Trans. Inform. Theory,
IT-21:698–699.
Gelb, A. (1989). Applied Optimal Estimation. The Analytic
Sciences Corporation.
Kailath, T., Sayed, A., and Hassibi, B. (2000). Linear Esti-
mation. Prentice Hall.
Kalman, R. E. and Bucy, R. S. (1961). New Results
in Linear Filtering and Prediction Theory. Trans.
ASME, J. Basic Engineering, Ser. D, 83:95–108. In:
Epheremides, A. and Thomas, J.B. (Ed.) 1973. Ran-
dom Processes. Multiplicity Theory and Canonical
Decompositions.
Navarro-Moreno, J., Ruiz-Molina, J., and Fern
´
andez, R. M.
(2003). Approximate Series Representations of
Second-Order Stochastic Processes. Applications to
Signal Detection and Estimation. IEEE, Trans. In-
form. Theory, 49(6):1574–1579.
Sugisaka, M. (1983). The Design of On-line Least-Squares
Estimators Given Covariance Specifications Via an
Imbedding Method. Applied Mathematics and Com-
putation, (13):55–85.
Van Trees, H. L. (1968). Detection, Estimation, and Modu-
lation Theory-Part I. Wiley, New York.
ON THE LINEAR LEAST-SQUARE PREDICTION PROBLEM
335