# Linear Estimation of Stationary Autoregressive Processes

Authors: Reza Dianat; Farokh Marvasti
Journal: ISRN Signal Processing
 (2011)

---

## Abstract

Consider a sequence of anmth-order Autoregressive (AR) stationary discrete-time process and assume that at
least m−1 consecutive neighboring samples of an unknown sample are available. It is not important that the neighbors
are from one side or are from both the left and right sides. In this paper, we find explicit solutions for the optimal linear
estimation of the unknown sample in terms of the neighbors. We write the estimation errors as the linear combination
of innovation noises. We also calculate the corresponding mean square errors (MSE). To the best of our knowledge,
there is no explicit solution for this problem. The known solutions are the implicit ones through orthogonality equations.
Also, there are no explicit solutions when fewer than m−1 samples are available. The order of the process (m) and the
feedback coefficients are assumed to be known.


---

## Body

## 1. Introduction

Estimation has many applications in different areas including compression and equalization [1, 2]. The linear estimation is more common due to its mathematical simplicity. The optimal linear estimation of a random variable x in terms of y1, y2, and yn is the following linear combination(1)x̂≜Ê{x∣y1,y2,…,yn}=∑i=1nAiyi,
where the coefficients Ai must be chosen to minimize the MSE E{(x-x̂)2} and E{·} stands for the expected value. To minimize the MSE, we must choose Ai’s to satisfy the orthogonality principle as follows:
(2)E{(x-x̂)yi}=0,i=1,2,…,n.
We also write the above condition as(3)x-x̂⊥yi,i=1,2,…,n.
Therefore, in the optimal linear estimation, we search for the coefficients such that the error is orthogonal to the data.A common model for many signals including image, speech, and biological signals is the AR model [1, 3–5]. This model has applications in different areas including detection [6, 7], traffic modeling [8], channel modeling [9], and forecasting [10]. An AR process is the output of an all-pole causal filter whose input is a white sequence called innovation noise [11]. We introduce another model for the process using an all-pole anticausal filter as well. The optimal linear estimation of an AR process is accomplished through the recursive solution of Yule-Walker (YW) equations using Levinson-Durbin algorithm [12]. This solution is recursive and implicit. As we will see in some cases the equation coefficients do not form a Toeplitz matrix and we cannot enjoy the complexity reduction advantage of Levinson algorithm.To the best of our knowledge, there is no explicit solution for YW equations. Most of the focus of researchers is on model parameters estimation from observations. When researchers arrive at YW equations, they stop, since they consider the solution as known through Levinson recursion. Broersen in his method for autocorrelation function estimation form observations points to YW equations and mainly concentrates on bias reduction in estimation using finite set of observations [13, 14]. He does not attempt to find the solution for YW equations. Fattah et al. try to estimate the autocorrelation function of an ARMA model from noisy data; they again refer to YW equation set and its solution using matrix inversion and no explicit solution is proposed [15]. Xia and Kamel propose an optimization method to estimate AR model parameters from noisy data [16]. Noise is not necessarily Gaussian. The method finds a minimum for a cost function and exploits a neural-network algorithm. Again, the explicit solution of the orthogonality equations is not the goal of the paper. Hsiao proposes an algorithm to estimate the parameters of a time-varying AR system [17]. He considers the feedback coefficients of a time-varying AR process as random variables. The proposed algorithm maximizes a posteriori probabilities conditioned on the data. The recursive algorithm is compared to Monte Carlo simulation in terms of accuracy and complexity. In this paper, the aim is parameter estimation from data and not the analytic solution of orthogonality equations. In [18], a sequence of Gaussian AR vector is considered. As the sequence elements are vectors rather than scalars, the AR model is defined by matrix feedback coefficients rather than scalar feedback coefficients. The estimation here is more complex, and some independence conditions are assumed. The method is based on convex optimization, and no exact answer can be provided. Mahmoudi and Karimi propose an LS-based method to estimate AR parameters from noisy data [19]. The method exploites YW equations, but this method also does not provide the explicit solution to the equations. Another LS-based estimation method can be seen in [20].As mentioned above, we could not see the final solution to YW orthogonality equations in the literature. In this work we have derived explicit solutions for orthogonality equations for different cases. Consider a stationarymth order AR process. The order and the feedback coefficients of the process are assumed to be known, and the model parameter estimation is out of the scope of this paper. The main goal of this paper is finding the solution for the orthogonality equations. We will find the the optimal linear estimation of a sample in terms of the neighbors where at least m-1 consecutive neighbors are available. The consecutive neighbors include the situations where all the m-1 or more neighbors are in one side, or some of them are left neighbors and the others are right neighbors. We will show that no more that m consecutive neighbors in each side are needed. Our approach is to find orthogonal estimation errors that are linear combinations of data. We use the well-known causal LTI AR model as well as our anticausal model to form orthogonal errors. The errors are formed as a linear combination of causal and anticausal innovation (process) noises. Beginning from suitable errors that are both orthogonal to the data and are linear combination of data, we arrive at linear estimations. We seek LTI system approach rather than trying to directly solve the orthogonality equations. The results of this paper for different cases can be important in situations where the equation matrices are ill-posed and the matrix inversion and other recursive algorithms become unstable.This paper is organized as follows. In Section2, the causal model is reviewed and the anticausal model is introduced. In Section 3, we review the forward prediction problem. We state the problem symmetries in Section 4. We see how we can use the similarities between two problems to exploit the solution of one problem to find the solution of the other problem. In Section 5, we extract a number of relations for cross-correlation functions that will be used later. We find the interpolation formulae when infinite data are available in Section 6. We find the prediction and interpolation with finite data in Sections 7 and 8, respectively. In Section 9, we present a detailed example to show that our relations and the matrix solution of the orthogonality principle result in the same coefficients. Finally, we conclude the work in Section 10.


## 2. Causal and Anticausal Models

A discrete-time stationary AR processsn of order m is modeled as follows.(4)sn+a1sn-1+a2sn-2+⋯+amsn-m=In,n∈Z.
The above equation is meant for a causal LTI system. In, the input of the system, is called the innovation noise and is a stationary white sequence with the zero expected value, that is, E{InIk}=σ2δ[n-k] and E{In}=0, where σ is a positive constant. δ[0]=1 and δ[i]=0 elsewhere. The system is causal. Therefore sn, the output of the system in the time index n, is a linear combination of the inputs in the time index n and before. So, we can write(5)sn=h0In+h1In-1+h2In-2+⋯=∑i=0∞hiIn-i.
In the above equation, hn is the impulse response of the system. Assuming the causal system model, we have hn=0 for n<0. Paying attention to the whiteness of the sequence {In} and from (5) we get the following result. 						(6)In+k⊥sn,k>0,n∈Z.Figure1 is the causal model of the AR process. H(z) is the Z-transform of hn, which is defined as(7)H(z)=∑k=-∞∞hkz-k.
For the system defined by (4), we have(8)H(z)=1A(z)=11+a1z-1+⋯+amz-m.Figure 1
The causal model.Assuming a stable causal system, we conclude that the roots ofA(z)=0 must be inside the unit circle |z|=1. The power spectral density function (PSDF) of a process is the Z-transform of its autocorrelation function. The PSDF of sn is [11](9)Ss(z)=SI(z)H(z)H(z-1)=σ2H(z)H(z-1).
In the above equation Ss(z) is the PSDF of sn and SI(z) is the PSDF of In.We now present the anticausal model. If we apply the sequencesn to an LTI system with the transfer function H-1(z-1), we get another innovation noise called In′. Figure 2 demonstrates the generation of the new innovation noise. To see the whiteness of the sequence In′, note that the PSDF of In′ by using Figure 2 and (9) is as follows.(10)SI′(z)=Ss(z)H-1(z-1)H-1(z)=σ2H(z)H(z-1)H-1(z-1)H-1(z)=σ2.Figure 2
Generation of another innovation noise.Equivalently we can applyIn′ to the inverse system with the transfer function H′(z)=H(z-1) to get sn. The generation of sn from In′ is depicted in Figure 3.Figure 3
Anticausal model.We have(11)H′(z)=H(z-1)=1A(z-1).
Therefore hn′=h-n. Noting that hn=0 for n<0, we see that hn′=0 for n>0. Also note that the roots of A(z-1)=0 are outside the unit circle, as we had the roots of A(z)=0 inside the unit circle. Regarding these points, we know that the system with the transfer function H′(z) is stable and anticausal. We have(12)H′(z)=11+a1z+a2z2+⋯+amzm.Using the above equation and Figure3, we get(13)sn+a1sn+1+a2sn+2+⋯+amsn+m=In′,n∈Z.Also, note that(14)sn=∑i=-∞∞hi′In-i′=h0′In′+h-1′In+1′+h-2′In+2′+⋯=h0In′+h1In+1′+⋯=∑i=0∞hiIn+i′.From (14) and Figure 3, we see that sn is a linear combination of In′ and the inputs after that. The whiteness of the sequence {In′} gives then(15)In-k′⊥sn,n∈Z,k>0.


## 3. Forward Prediction

Forward prediction can be accomplished by using the whitening filter [11]. The data are whitened, and we use the equivalent white data to achieve the prediction. As an example, consider the 1-step forward prediction of sn. It is seen that sn is estimated as(16)ŝn=Ê{sn∣sn-k,k>0}=-∑k=1maksn-k=-a1sn-1-a2sn-2-⋯-amsn-m.
It can bee seen from (4) that the error sn-ŝn is equal to In and therefore, from (6), it is orthogonal to sn-k for k>0. It proves the optimality of (16).The 2-step prediction can be done as [11](17)ŝn=Ê{sn∣sn-k,k≥2}=-a1ŝn-1-∑i=2maisn-i.
In the above equation, ŝn-1 is the prediction of sn-1 from its previous data (1-step prediction) and is obtained by replacing n by n-1 in (16).(18)ŝn-1=Ê{sn-1∣sn-k,k≥2}=-∑k=1maksn-k-1=-a1sn-2-a2sn-3-⋯-amsn-m-1.
From (17), (18), and (4), the estimation error is (19)en=sn+∑i=2maisn-i-a1∑k=1maksn-k-1=In-a1sn-1-a1∑k=1maksn-k-1=In-a1In-1.From (6), it is clear that In and In-1 are orthogonal to sn-k for k≥2. It proves the optimality of (17).The higher-order predictions can be obtained in the same manner. As the final example of this section, consider the 3-step forward prediction that is accomplished as follows.(20)ŝn=Ê{sn∣sn-k,k≥3}=-a1ŝn-1-a2ŝn-2-∑k=3maksn-k.In the above equation,ŝn-1 and ŝn-2 are the 2-step and 1-step predictions of sn-1 and sn-2, respectively, and are obtained from (17) and (16). The error is(21)en=sn+a1ŝn-1+a2ŝn-2+∑i=3maisn-i=In-a1sn-1-a2sn-2+a1ŝn-1+a2ŝn-2=In-a1(sn-1-ŝn-1)-a2(sn-2-ŝn-2)=In-a1(In-1-a1In-2)-a2In-2.


## 4. The Problem Symmetries

Consider the following linear interpolation ofsn from the data around it:(22)ŝn=Ê{sn∣sn-k1,sn-k1+1,…,sn-1,sn+1,…,sn+k2}=a-k1′sn-k1+a-k1+1′sn-k1+1+⋯+ak2′sn+k2.
The orthogonality principle gives(23)E{(sn-a-k1′sn-k1-a-k1+1′sn-k1+1-⋯-ak2′sn+k2)sn+i}=0,i=-k1,-k1+1,…,k2,i≠0.
The above equations become(24)Rs[i+k1]a-k1′+Rs[i+k1-1]a-k1+1′+⋯+Rs[i-k2]ak2′=Rs[i],i=-k1,-k1+1,…,k2,i≠0.
In the above equations, Rs[i]=E{snsn-i}.Now, consider the following estimation.(25)ŝn=Ê{sn∣sn-k2,sn-k2+1,…,sn-1,sn+1,…,sn+k1}=ak1′′sn+k1+ak1-1′′sn+k1-1+⋯+a-k2′′sn-k2.
The orthogonality of error to the data gives(26)E{(sn-ak1′′sn+k1-ak1-1′′sn+k1-1-⋯-a-k2′′sn-k2)sn+i}=0,i=k1,k1-1,…,-k2,i≠0.
They become(27)Rs[i-k1]ak1′′+Rs[i-k1+1]ak1-1′′+⋯+Rs[i+k2]ak2′′=Rs[i],i=k1,k1-1,…,-k2,i≠0.
Regarding that the Rs[·] is an even function, we notice that the set of equations (24) and the set of equations (27) are exactly the same. Therefore,(28)a-k1′=ak1′′,a-k1+1′=ak1-1′′,…,ak2′=a-k2′′.As an example, consider the following backward prediction.(29)ŝn=Ê{sn∣sn+k,k>0}.
Using (16) and the symmetry, we get(30)ŝn=Ê{sn∣sn+k,k>0}=-∑k=1maksn+k=-a1sn+1-a2sn+2-⋯-amsn+m.
The validity of the solution can also be confirmed as from (13), it is seen that the estimation error is(31)sn+a1sn+1+a2sn+2+⋯+amsn+m=In′.
Using (15), it is clear that the error is orthogonal to the data. It proves the optimality of (30).


## 5. Cross-Correlation Functions

In this section, we derive a number of properties for the cross-correlations between innovation noises and the AR process. We will exploit these properties to prove our solutions.We defineRsI[k]=E{snIn-k} and RI′s[k]=E{In′sn-k}. The first simple property follows from (6) and (15) as follows.(32)RsI[k]=RI′s[k]=0,k<0.
Now, consider Figure 1. In this figure In is the input and sn is the output. The impulse response of system is hn≜h[n]. Therefore, we have [11](33)RsI[k]=RI[k]*h[k]=σ2δ[k]*h[k]=σ2h[k].
In this equation, RI[k]=E{InIn-k} and the “*” operator is the discrete convolution. Taking the Z-transform from both sides of (33) and using (8), we get(34)SsI(z)=σ2H(z)=σ21+a1z-1+⋯+amz-m.
Or equivalently(35)SsI(z)(1+a1z-1+⋯+amz-m)=σ2.
Taking inverse Z-transform from this equation, we have(36)RsI[k]+a1RsI[k-1]+⋯+amRsI[k-m]=σ2δ[k].
The right side of (36) is zero for k≠0.Referring to Figure3, we have [11](37)RI′s[k]=RI′[k]*h′[-k]=σ2δ[k]*h′[-k]=σ2h′[-k]=σ2h[k].
Again, we conclude that(38)RI′s[k]+a1RI′s[k-1]+⋯+amRI′s[k-m]=σ2δ[k].


## 6. Interpolation Using an Infinite Set of Data

In this section, we assume that infinite number of data are available. However, we will see that only a finite number of data are sufficient.


### 6.1. Infinite Data on the Left Side

We want to obtain the following estimation.(39)ŝn=Ê{sn∣sn+i,i≤k1,i≠0}.k1 is a positive integer constant not greater than m. There are k1 data available on the right side of sn and infinite data on the left side. Define a0≜1. We are going to prove the following.(40)ŝn=Ê{sn∣sn+i,i≤k1,i≠0}=-1∑k=0k1ak2(∑k=1k1(∑p=0k1-kapap+k)sn+k+∑k=1m-k1(∑p=0k1apap+k)sn-k+∑k=m-k1+1m(∑p=0m-kapap+k)sn-k).
Observe from (40) that although there are infinite data on the left side of sn, only m data sn-1 to sn-m participate in the estimation. Indeed, (40) is the optimal linear estimation solution for ŝn=Ê{sn∣sn+i,-k2≤i≤k1,i≠0}, where k2 can be any integer greater than or equal to m.To prove the optimality of (40), we must show that the estimation error is orthogonal to the data. Firstly the estimation error can be calculated by inserting ŝn from (40) in en=sn-ŝn. Secondly, by extending the innovation noises using (4) we can confirm that(41)en=sn-ŝn=1∑k=0k1ak2(In+a1In+1+⋯+ak1In+k1).
Indeed, we have obtained (40) from (41). The motivation is that the estimation error has to possess two essential conditions: (1) it must be orthogonal to the data and (2) it must be only a linear combination of the data and the variable to be estimated. It remains to prove that the right side of (41) is orthogonal to the data.Using (6), it is quite clear that In to In+k1 are orthogonal to sn-k for k>0, and so is en in (41). Further, we have(42)E{sn+i(In+a1In+1+⋯+ak1In+k1)}=RsI[i]+a1RsI[i-1]+⋯+ak1RsI[i-k1]=RsI[i]+a1RsI[i-1]+⋯+aiRsI[0],1≤i≤k1.
The last equation of (42) is justified as we have RsI[k]=0 for k<0 from (32). Using (32), (36), (41), and (42) it is seen that(43)E{(In+a1In+1+⋯+ak1In+k1)sn+i}=0,1≤i≤k1.
This completes the proof.The MSE is(44)E{en2}=1(∑k=0k1ak2)2⋅E{(In+a1In+1+⋯+ak1In+k1)2}=1(∑k=0k1ak2)2⋅(E{In2}+a12E{In+12}+⋯+ak12E{In+k12})=1(∑k=0k1ak2)2⋅(σ2+a12σ2+⋯+ak12σ2).Therefore,(45)E{en2}=σ2∑k=0k1ak2.


### 6.2. Infinite Data on the Right Side

By symmetry, and replacingsn-k by sn+k in (40), the following estimation is derived.(46)ŝn=Ê{sn∣sn-i,i≤k1,i≠0}=-1∑k=0k1ak2(∑k=1k1(∑p=0k1-kapap+k)sn-k+∑k=1m-k1(∑p=0k1apap+k)sn+k+∑k=m-k1+1m(∑p=0m-kapap+k)sn+k).Again, onlym data sn+1 to sn+m on the right side of sn participate in the interpolation, and the data after them are not needed. Therefore, (46) is the solution for all the optimal linear interpolations ŝn=Ê{sn∣sn-i,-k2≤i≤k1,i≠0}, where k2 can be any integer greater than or equal to m.The validity of (46) can also be proved as follows. The error is calculated as en=sn-ŝn, where ŝn is from (46). By extending the innovation noises from (13), it can be verified that(47)en=sn-ŝn=1∑k=0k1ak2(In′+a1In-1′+⋯+ak1In-k1′).
Using (15), it is quite clear that In-k1′ to In′ are orthogonal to sn+k for k>0, and so is en in (47). Further, we have(48)E{sn-i(In′+a1In-1′+⋯+ak1In-k1′)}=RI′s[i]+a1RI′s[i-1]+⋯+ak1RI′s[i-k1]=RI′s[i]+a1RI′s[i-1]+⋯+aiRI′s[0],1≤i≤k1.
The last equation of (48) is justified as we have RI′s[k]=0 for k<0 from (32). Using (32), (38), (47), and (48), it is seen that E{ensn-i}=0 for 1≤i≤k1. This completes the proof.The MSE is the same as in (45).


### 6.3. Infinite Data on Both Sides

Now, we want to estimatesn from all the data around it. We will see that only m data on each side are needed and as is expected, the data with the same distance from sn participate with the same weight. We have(49)ŝn=Ê{sn∣sn-i,i≠0}=-1∑k=0mak2⋅(∑k=1m(∑p=0m-kapap+k)(sn-k+sn+k)).
This estimation can also be obtained by letting k1=m in (40) or (46). Again, note that (49) is the optimal solution for the problems ŝn=Ê{sn∣sn-i,i≠0,-k1≤i≤k2}, where k1 and k2 can be any integer greater than or equal to m.The validity of (49) can also be proved as follows. The error is calculated as en=sn-ŝn, where ŝn is from (49). By extending the innovation noises from (4), it can be verified that(50)en=sn-ŝn=1∑k=0mak2(In+a1In+1+⋯+amIn+m).
Using (6) it is quite clear that In to In+m are orthogonal to sn-k for k>0, and so is en in (50). Further, we have(51)E{sn+i(In+a1In+1+⋯+amIn+m)}=RsI[i]+a1RsI[i-1]+⋯+amRsI[i-m],i>0.
Using (32), (36), (50), and (51), it is seen that E{ensn+i}=0 for i>0. This completes the proof.The MSE is(52)E{en2}=1(∑k=0mak2)2⋅E{(In+a1In+1+⋯+amIn+m)2}=σ2∑k=0mak2.


## 6.1. Infinite Data on the Left Side

We want to obtain the following estimation.(39)ŝn=Ê{sn∣sn+i,i≤k1,i≠0}.k1 is a positive integer constant not greater than m. There are k1 data available on the right side of sn and infinite data on the left side. Define a0≜1. We are going to prove the following.(40)ŝn=Ê{sn∣sn+i,i≤k1,i≠0}=-1∑k=0k1ak2(∑k=1k1(∑p=0k1-kapap+k)sn+k+∑k=1m-k1(∑p=0k1apap+k)sn-k+∑k=m-k1+1m(∑p=0m-kapap+k)sn-k).
Observe from (40) that although there are infinite data on the left side of sn, only m data sn-1 to sn-m participate in the estimation. Indeed, (40) is the optimal linear estimation solution for ŝn=Ê{sn∣sn+i,-k2≤i≤k1,i≠0}, where k2 can be any integer greater than or equal to m.To prove the optimality of (40), we must show that the estimation error is orthogonal to the data. Firstly the estimation error can be calculated by inserting ŝn from (40) in en=sn-ŝn. Secondly, by extending the innovation noises using (4) we can confirm that(41)en=sn-ŝn=1∑k=0k1ak2(In+a1In+1+⋯+ak1In+k1).
Indeed, we have obtained (40) from (41). The motivation is that the estimation error has to possess two essential conditions: (1) it must be orthogonal to the data and (2) it must be only a linear combination of the data and the variable to be estimated. It remains to prove that the right side of (41) is orthogonal to the data.Using (6), it is quite clear that In to In+k1 are orthogonal to sn-k for k>0, and so is en in (41). Further, we have(42)E{sn+i(In+a1In+1+⋯+ak1In+k1)}=RsI[i]+a1RsI[i-1]+⋯+ak1RsI[i-k1]=RsI[i]+a1RsI[i-1]+⋯+aiRsI[0],1≤i≤k1.
The last equation of (42) is justified as we have RsI[k]=0 for k<0 from (32). Using (32), (36), (41), and (42) it is seen that(43)E{(In+a1In+1+⋯+ak1In+k1)sn+i}=0,1≤i≤k1.
This completes the proof.The MSE is(44)E{en2}=1(∑k=0k1ak2)2⋅E{(In+a1In+1+⋯+ak1In+k1)2}=1(∑k=0k1ak2)2⋅(E{In2}+a12E{In+12}+⋯+ak12E{In+k12})=1(∑k=0k1ak2)2⋅(σ2+a12σ2+⋯+ak12σ2).Therefore,(45)E{en2}=σ2∑k=0k1ak2.


## 6.2. Infinite Data on the Right Side

By symmetry, and replacingsn-k by sn+k in (40), the following estimation is derived.(46)ŝn=Ê{sn∣sn-i,i≤k1,i≠0}=-1∑k=0k1ak2(∑k=1k1(∑p=0k1-kapap+k)sn-k+∑k=1m-k1(∑p=0k1apap+k)sn+k+∑k=m-k1+1m(∑p=0m-kapap+k)sn+k).Again, onlym data sn+1 to sn+m on the right side of sn participate in the interpolation, and the data after them are not needed. Therefore, (46) is the solution for all the optimal linear interpolations ŝn=Ê{sn∣sn-i,-k2≤i≤k1,i≠0}, where k2 can be any integer greater than or equal to m.The validity of (46) can also be proved as follows. The error is calculated as en=sn-ŝn, where ŝn is from (46). By extending the innovation noises from (13), it can be verified that(47)en=sn-ŝn=1∑k=0k1ak2(In′+a1In-1′+⋯+ak1In-k1′).
Using (15), it is quite clear that In-k1′ to In′ are orthogonal to sn+k for k>0, and so is en in (47). Further, we have(48)E{sn-i(In′+a1In-1′+⋯+ak1In-k1′)}=RI′s[i]+a1RI′s[i-1]+⋯+ak1RI′s[i-k1]=RI′s[i]+a1RI′s[i-1]+⋯+aiRI′s[0],1≤i≤k1.
The last equation of (48) is justified as we have RI′s[k]=0 for k<0 from (32). Using (32), (38), (47), and (48), it is seen that E{ensn-i}=0 for 1≤i≤k1. This completes the proof.The MSE is the same as in (45).


## 6.3. Infinite Data on Both Sides

Now, we want to estimatesn from all the data around it. We will see that only m data on each side are needed and as is expected, the data with the same distance from sn participate with the same weight. We have(49)ŝn=Ê{sn∣sn-i,i≠0}=-1∑k=0mak2⋅(∑k=1m(∑p=0m-kapap+k)(sn-k+sn+k)).
This estimation can also be obtained by letting k1=m in (40) or (46). Again, note that (49) is the optimal solution for the problems ŝn=Ê{sn∣sn-i,i≠0,-k1≤i≤k2}, where k1 and k2 can be any integer greater than or equal to m.The validity of (49) can also be proved as follows. The error is calculated as en=sn-ŝn, where ŝn is from (49). By extending the innovation noises from (4), it can be verified that(50)en=sn-ŝn=1∑k=0mak2(In+a1In+1+⋯+amIn+m).
Using (6) it is quite clear that In to In+m are orthogonal to sn-k for k>0, and so is en in (50). Further, we have(51)E{sn+i(In+a1In+1+⋯+amIn+m)}=RsI[i]+a1RsI[i-1]+⋯+amRsI[i-m],i>0.
Using (32), (36), (50), and (51), it is seen that E{ensn+i}=0 for i>0. This completes the proof.The MSE is(52)E{en2}=1(∑k=0mak2)2⋅E{(In+a1In+1+⋯+amIn+m)2}=σ2∑k=0mak2.


## 7. Prediction with Finite Data

Assume that onlym-1 consecutive data sn-1 to sn-m+1 are available. We want to prove the following.(53)ŝn=Ê{sn∣sn-k,1≤k≤m-1}=-11-am2∑k=1m-1(ak-amam-k)sn-k.The above estimation can be obtained as follows. Sincesn-m is not available we can estimate it from data sn-1 to sn-m+1. The estimated value can be now used to predict sn using (16).(54)ŝn=Ê{sn∣sn-k,1≤k≤m-1}=-∑k=1m-1aksn-k-amŝn-m=-a1sn-1-a2sn-2-⋯-am-1sn-m+1-amŝn-m.
On the other hand, sn-m can be backward predicted using (30) as(55)ŝn-m=Ê{sn-m∣sn-k,1≤k≤m-1}=-a1sn-m+1-a2sn-m+2-⋯-am-1sn-1-amŝn.
Now we have two equations (54) and (55) with two unknowns ŝn and ŝn-m. Solving these equations, we get (53). The optimality of (53) can also be proved by seeing that the estimation error is equal to(56)en=In-amIn-m′1-am2.
To derive the above equation, we has used (4) and (13). It is easily seen from (6) and (15) that In and In-m′ are orthogonal to data sn-1 to sn-m+1. This proves the optimality of (53). To calculate the MSE, we note that(57)E{en2}=E{en(sn-ŝn)}=E{ensn}.
The last equation is justified, as the error is orthogonal to the data and to the estimation which is a linear combination of the data. Inserting (56) in (57), we get(58)E{ensn}=11-am2⋅E{(In-amIn-m′)sn}=11-am2⋅(RsI[0]-amRI′s[-m]).
Finally, using (58), (32), and (36), we have(59)E{en2}=σ21-am2.Higher-order predictions withm-1 data can be obtained from (53). As an example, we have(60)ŝn=Ê{sn∣sn-k,2≤k≤m}=-a1ŝn-1-∑k=2maksn-k,
where ŝn-1 is derived by replacing n by n-1 in (53).We could not derive a simple general form for the estimation with less thanm-1 data.


## 8. Interpolation with Finite Data

We now derive the linear interpolation with less thanm data on each side. More clearly we allege(61)ŝn=Ê{sn∣sn+k,-k2≤k≤k1,k≠0}=-1∑k=0k1ak2-∑k=k2+1mak2×(∑k=m-k2k1(∑p=0k1-kapap+k)sn+k+∑k=1m-k2-1(∑p=0k1-kapap+k-∑p=k2+1m-kapap+k)sn+k+∑k=1m-k1-1(∑p=0k1apap+k-∑p=k2-k+1m-kapap+k)sn-k+∑k=m-k1k2(∑p=0k2-kapap+k)sn-k).
In (61) we must have k1+k2≥m-1 and k1≤k2≤m-1. It means that the distance between sn and the farthest data on the right side is less than the distance between sn and the farthest data on the left side. The optimality of (61) can be seen as we can verify that from (61), (4), and (13) the estimation error is(62)en=1∑k=0k1ak2-∑k=k2+1mak2⋅(In+a1In+1+⋯+ak1In+k1-amIn-m′-am-1In-m+1′-⋯-ak2+1In-k2-1′).
It remains to prove that (62) is orthogonal to the data.  (1)
It is clear from (6) and (15) that In to In+k1 and In-m′ to In-k2-1′ are orthogonal to the data sn-1 to sn-k2. Therefore the error in (62) is orthogonal to sn-k for 1≤k≤k2.(2)
Further from (43) and regarding that In-m′ to In-k2-1′ are orthogonal to the data sn+1 to sn+k1 according to (15), we see that the error in (62) is orthogonal to sn+k for 1≤k≤k1.Therefore the error is orthogonal to the data and the proof is completed.From (32), (36), and (62), the MSE is(63)E{en2}=E{ensn}=1∑k=0k1ak2-∑k=k2+1mak2⋅(RsI[0]+a1RsI[-1]+⋯+RsI[-k1]-amRI′s[-m]-am-1RI′s[-m+1]⋯-ak2+1RI′s[-k2-1])=σ2∑k=0k1ak2-∑k=k2+1mak2.
For the case k1=k2,  2k1≥m-1,  k1≤m-1, we can replace k2 by k1 in (61) to achieve the following.(64)ŝn=Ê{sn∣sn+k,-k1≤k≤k1,k≠0}=-1∑k=0k1ak2-∑k=k1+1mak2⋅(∑k=m-k1k1(∑p=0k1-kapap+k)(sn-k+sn+k)+∑k=1m-k1-1(∑p=0k1-kapap+k-∑p=k1+1m-kapap+k)(sn-k+sn+k)).
As expected, we see that the data with the same distance from sn participate with the same weight.Now, consider the case that the distance betweensn and the farthest data on the right side is more than the distance between sn and the farthest data on the left side. It can be handled by the symmetry of the problem. More clearly, if we replace sn-k by sn+k and vice versa in (61), we get the following.(65)ŝn=Ê{sn∣sn-k,-k2≤k≤k1,k≠0}=-1∑k=0k1ak2-∑k=k2+1mak2×(∑k=m-k2k1(∑p=0k1-kapap+k)sn-k+∑k=1m-k2-1(∑p=0k1-kapap+k-∑p=k2+1m-kapap+k)sn-k+∑k=1m-k1-1(∑p=0k1apap+k-∑p=k2-k+1m-kapap+k)sn+k+∑k=m-k1k2(∑p=0k2-kapap+k)sn+k).
Again in (65), k1≤k2≤m-1 and k1+k2≥m-1. The estimation error in this case is(66)en=1∑k=0k1ak2-∑k=k2+1mak2⋅(In′+a1In-1′+⋯+ak1In-k1′-amIn+m-am-1In+m-1-⋯-ak2+1In+k2+1In′+a1In-1′).
The MSE is the same as (63). We could not find a simple general form for the case k1+k2<m-1.


## 9. A Detailed Example

In this section we deal with a detailed example. The optimal linear estimation of the following process is desired.(67)sn+0.8sn-1+0.3sn-2-0.1sn-3=In.In is the innovation noise with the unit variance σ=1. We have a1=0.8, a2=0.3 and a3=-0.1. The process is the response of the following 3rd order  (m=3) all-pole filter to the innovation noise.(68)H(z)=11+0.8z-1+0.3z-2-0.1z-3.
The poles of this system are p1=0.2 and p2,3=-0.5±j0.5. Taking inverse Z-transform from Ss(z)=H(z)H(z-1), we get the following autocorrelation function.(69)Rs[k]=rk=E{snsn-k}=62513542×5-∣n∣+402257×2-∣n∣/2(103cos⁡(3π4n)-26sin(3π4|n|)).
From (69), we have r0=1.8716, r1=-1.1339, r2=0.2322, r3=0.3415, r4=-0.4563, r5=0.2858, and r6=-0.0576. Now, we consider different cases.


### 9.1. Prediction with Finite Data

We want to derive the following optimal linear prediction.(70)ŝn=Ê{sn∣sn-1,sn-2}=A1sn-1+A2sn-2.
Using (53), we have(71)ŝn=-11-0.01[(0.8+0.1×0.3)sn-1+(0.3+0.1×0.8)sn-2]=-0.8384sn-1-0.3838sn-2.
If we want to verify the solution using the orthogonality equations, we have(72)E{(sn-A1sn-1-A2sn-2)sn-k}=0,k=1,2.
Expanding (72), we get(73)r0A1+r1A2=r1,r1A1+r0A2=r2,
where rk’s come from (69). Replacing rk’s from (69) in (73), we get(74)1.8716A1-1.1339A2=-1.1339,-1.1339A1+1.8716A2=0.2322,
Solving (74), we get the same result as (71).


### 9.2. Interpolation with Finite Data

Consider the following problem.(75)ŝn=Ê{sn∣sn-1,sn+1}=A1sn-1+A1′sn+1
It is the symmetric case of k1=k2=1 and we have 2k1=2=m-1. Using (64), we have(76)ŝn=-[1×0.8-0.3×(-0.1)]1+0.64-0.09-0.01(sn-1+sn+1)=-0.5390(sn-1+sn+1).
Let us rederive the solution of (75) using the orthogonality conditions. We have(77)E{(sn-A1sn-1-A1′sn+1)sn-k}=0,k=1,-1.
Expanding (77), we get the following.(78)r0A1+r2A1′=r1,r2A1+r0A1′=r1.
Solving (78), we get the same answer as (76).Now, consider the nonsymmetric following problem.(79)ŝn=Ê{sn∣sn-2,sn-1,sn+1}=A1sn+1+A1′sn-1+A2′sn-2
which is the case of k1=1<k2=2≤m-1, and k1+k2≥m-1. From (61), we get the following results.(80)ŝn=-11+0.64-0.01⋅(1×0.8sn+1+(1×0.8+0.8×0.3-0.3×(-0.1))×sn-1+1×0.3sn-2)=-0.4908sn+1-0.6564sn-1-0.1840sn-2.
Now, we want to obtain the solution of (79) using the matrix equations and we expect the same answer as (80). The orthogonality condition is(81)E{(sn-A1sn+1-A1′sn-1-A2′sn-2)sn-k}=0,k=-1,1,2.
It follows that(82)r0A1+r2A1′+r3A2′=r1,r2A1+r0A1′+r1A2′=r1,r3A1+r1A1′+r0A2′=r2.
The result of (82) is the same as (80).


### 9.3. Interpolation with Infinite Data on the Left Side

We want to obtain the following estimation.(83)ŝn=Ê{sn∣sn+i,i≤1,i≠0}=A1sn+1+A1′sn-1+A2′sn-2+A3′sn-3.
We can do it if we let k1=1 in (40). It follows that(84)ŝn=-11+0.64⋅(1×0.8sn+1+(1×0.8+0.8×0.3)sn-1+(1×0.3+0.8×(-0.1))sn-2+1×(-0.1)sn-3)=-0.4878sn+1-0.6341sn-1-0.1341sn-2+0.0610sn-3.Now we verity (84) using the orthogonality conditions.(85)E{(sn-A1sn+1-A1′sn-1-A2′sn-2-A3′sn-3)sn-k}=0,k=-1,1,2,3.
The following set of equations is obtained(86)r0A1+r2A1′+r3A2′+r4A3′=r1,r2A1+r0A1′+r1A2′+r2A3′=r1,r3A1+r1A1′+r0A2′+r1A3′=r2,r4A1+r2A1′+r1A2′+r0A3′=r3.Note that the coefficient matrix of (86) is not Toeplitz. The result of (86) is the same as (84).


## 9.1. Prediction with Finite Data

We want to derive the following optimal linear prediction.(70)ŝn=Ê{sn∣sn-1,sn-2}=A1sn-1+A2sn-2.
Using (53), we have(71)ŝn=-11-0.01[(0.8+0.1×0.3)sn-1+(0.3+0.1×0.8)sn-2]=-0.8384sn-1-0.3838sn-2.
If we want to verify the solution using the orthogonality equations, we have(72)E{(sn-A1sn-1-A2sn-2)sn-k}=0,k=1,2.
Expanding (72), we get(73)r0A1+r1A2=r1,r1A1+r0A2=r2,
where rk’s come from (69). Replacing rk’s from (69) in (73), we get(74)1.8716A1-1.1339A2=-1.1339,-1.1339A1+1.8716A2=0.2322,
Solving (74), we get the same result as (71).


## 9.2. Interpolation with Finite Data

Consider the following problem.(75)ŝn=Ê{sn∣sn-1,sn+1}=A1sn-1+A1′sn+1
It is the symmetric case of k1=k2=1 and we have 2k1=2=m-1. Using (64), we have(76)ŝn=-[1×0.8-0.3×(-0.1)]1+0.64-0.09-0.01(sn-1+sn+1)=-0.5390(sn-1+sn+1).
Let us rederive the solution of (75) using the orthogonality conditions. We have(77)E{(sn-A1sn-1-A1′sn+1)sn-k}=0,k=1,-1.
Expanding (77), we get the following.(78)r0A1+r2A1′=r1,r2A1+r0A1′=r1.
Solving (78), we get the same answer as (76).Now, consider the nonsymmetric following problem.(79)ŝn=Ê{sn∣sn-2,sn-1,sn+1}=A1sn+1+A1′sn-1+A2′sn-2
which is the case of k1=1<k2=2≤m-1, and k1+k2≥m-1. From (61), we get the following results.(80)ŝn=-11+0.64-0.01⋅(1×0.8sn+1+(1×0.8+0.8×0.3-0.3×(-0.1))×sn-1+1×0.3sn-2)=-0.4908sn+1-0.6564sn-1-0.1840sn-2.
Now, we want to obtain the solution of (79) using the matrix equations and we expect the same answer as (80). The orthogonality condition is(81)E{(sn-A1sn+1-A1′sn-1-A2′sn-2)sn-k}=0,k=-1,1,2.
It follows that(82)r0A1+r2A1′+r3A2′=r1,r2A1+r0A1′+r1A2′=r1,r3A1+r1A1′+r0A2′=r2.
The result of (82) is the same as (80).


## 9.3. Interpolation with Infinite Data on the Left Side

We want to obtain the following estimation.(83)ŝn=Ê{sn∣sn+i,i≤1,i≠0}=A1sn+1+A1′sn-1+A2′sn-2+A3′sn-3.
We can do it if we let k1=1 in (40). It follows that(84)ŝn=-11+0.64⋅(1×0.8sn+1+(1×0.8+0.8×0.3)sn-1+(1×0.3+0.8×(-0.1))sn-2+1×(-0.1)sn-3)=-0.4878sn+1-0.6341sn-1-0.1341sn-2+0.0610sn-3.Now we verity (84) using the orthogonality conditions.(85)E{(sn-A1sn+1-A1′sn-1-A2′sn-2-A3′sn-3)sn-k}=0,k=-1,1,2,3.
The following set of equations is obtained(86)r0A1+r2A1′+r3A2′+r4A3′=r1,r2A1+r0A1′+r1A2′+r2A3′=r1,r3A1+r1A1′+r0A2′+r1A3′=r2,r4A1+r2A1′+r1A2′+r0A3′=r3.Note that the coefficient matrix of (86) is not Toeplitz. The result of (86) is the same as (84).


## 10. Conclusion

We introduced anticausal LTI model besides the known causal LTI model for AR processes. Using these models and the related innovation noises, we achieved the optimal linear interpolations for different cases. Specifically, we extracted the formulae when there are infinite data on the right, or the left sides of the variable to be estimated. We also obtained the linear prediction or interpolation with finite data. The number of data must be at least the order of the process minus one. We could not find a general simple form when fewer data are available. For the proofs of our solutions, the innovation noises and the orthogonality principle are essential.



---

*Source: 138683-2011-02-14.xml*