# Is Linear Prediction ever exact?

I'm just learning about linear prediction and was wondering whether or not there are any signals that would produce no error if run through a linear prediction algorithm. I was thinking (maybe naively) that if we have a linear signal (one that changes linearly with time) that we should be able to linearly predict this with no error. Is my intuition on this correct? Are there any other signals that are like this?

First of all, thanks so much for the replies! Secondly, I'm glad my intuition was correct, but I was having doubts in the first place because I couldn't exactly predict future samples of my signal no matter what my input signal was. For example, here's an image of me trying to get the linear prediction coefficients using 'lpc' function in Matlab. I've tried this for several of the types of signals suggested above, and didn't get the correct coefficients for any of them. Why does this happen? I doubt the 'lpc' function is incorrect so it just must be doing something different than what I thought it was doing.

Theoretically, yes. So you can for instance predict values taken by polynomials, with the following initial patterns:

• degree $$0$$: $$\hat{S}[n] = {S}[n-1]$$;
• degree $$1$$: $$\hat{S}[n] = 2{S}[n-1]-{S}[n-2]$$;
• degree $$2$$: $$\hat{S}[n] = 3{S}[n-1]-3{S}[n-2]+{S}[n-3]$$;
• degree $$3$$: $$\hat{S}[n] = 4{S}[n-1]-6{S}[n-2]+4{S}[n-3]-{S}[n-4]$$;

and so on. You can recognize binomial coefficients.

There are similar linear relations for other signals when sampling conditions are met, and for different cost functions. I am happy to dig into old stuff here. In a 1927, G. Udny Yule (the same as in autoregressive modeling known under Yule-Walker), On a Method of Investigating Periodicities in Disturbed Series, with Special Reference to Wolfer's Sunspot Numbers, gave the following trigonometric recurrence relation (using the same notations), for:

\begin{align} u_0 & =& A \sin\left({2\pi\frac{t+\tau}{T}}\right)\\ u_1 & =& A \sin\left({2\pi\frac{t+\tau+h}{T}}\right)\\ u_2 & =& A \sin\left({2\pi\frac{t+\tau+2h}{T}}\right)\end{align} then $$u_2 = (2-\mu)u_1-u_0$$ with $$\mu = 4 \sin^2 \pi\frac{h}{T}$$. One can notice that, when $$\mu =0$$, one recognizes the linear extrapolation: $$u_2 = 2u_1-u_0$$.

I would suggest:

In practice, the exactness is limited by the data precision (in time and amplitude), for instance by finite-word quantization (rounding errors, floating point operations) and jitter, in time.

• I was referring to the standard context of polynomial prediction – Laurent Duval Nov 2 '18 at 13:10
• I do second @OlliNiemitalo in that, however I think, least squres error with "0" error after minimization (hence exact true polynomial coefficients) is what he refers to... (i.e. fitting nth order polynomial to data generated by nth (or less) order polynomial model) – Fat32 Nov 2 '18 at 20:07
• Laurent, just to two .pdf references you supply make this a valuable answer. particularly the Vaidyanathan reference. thanks. – robert bristow-johnson Nov 2 '18 at 21:20
• @fat32 While it is not untrue under the least-squares context, I removed the mention. Indeed, I was in the frame of mind of a recent activity where I wanted to predict the next sample in a real-time context with forgetting factors, and the exact polynomial was then a special case. – Laurent Duval Nov 5 '18 at 10:12
• "polynomial signals can be predicted exactly from its past samples" would be enough :-)) – Fat32 Nov 5 '18 at 10:19

I'd like to use as definition of "exact (forward) linear prediction" that given a finite number of the first consecutive samples of a signal, all of the following samples can be predicted with zero residual error by a linear predictor with the same finite number of coefficients.

Your thinking is correct. Consider the linear discrete signal and a linear predictor:

\begin{cases}x[k] = a_0 + a_1 k&\text{(signal)}\\ x[k] = c_1 x[k - 1] + c_2 x[k - 2]&\text{(exact predictor)}\end{cases}\\ \begin{align}a_0 + a_1 k &= c_1 \big(a_0 + a_1 (k - 1)\big) + c_2 \big(a_0 + a_1 (k - 2)\big)\\ \Rightarrow a_0 + a_1 k &= c_1 (a_0 + a_1 k - a_1) + c_2 (a_0 + a_1 k - 2 a_1)\\ \Rightarrow a_0 + a_1 k &= c_1 a_0 + c_1 a_1 k - c_1 a_1 + c_2 a_0 + c_2 a_1 k - 2 c_2 a_1\end{align}\\ \Rightarrow\begin{cases} a_0 = c_1 a_0 - c_1 a_1 + c_2 a_0 - 2 c_2 a_1\\ a_1 = c_1 a_1 + c_2 a_1\end{cases}\\ \Rightarrow\begin{cases}c_1 = 2\\ c_2 = -1\end{cases}\\ \Rightarrow x[k] = 2x[k - 1] - x[k - 2]\quad\text{(exact predictor)}

Such a signal can be exactly predicted from the previous two samples. This is the degree 1 predictor from Laurent's answer.

A sinusoid of a known frequency $$\omega$$ and unknown phase and amplitude can be predicted from two previous samples. The recursive part of the filter in Goertzel algorithm does this, which can be confirmed by the following, using trigonometric identities $$\cos(\alpha)\cos(\beta) = \frac{\cos(\alpha - \beta) + \cos(\alpha + \beta)}{2}$$ and $$\cos(-\alpha) =\cos(\alpha):$$

$$\begin{cases}x[k] = A\cos(\omega k + \omega_0)&\text{(signal)}\\ x[k] = 2\cos(\omega)x[k-1] - x[k-2]&\text{(exact predictor)}\end{cases}\\ A\cos(\omega k + \omega_0) = 2\cos(\omega) A \cos\big(\omega (k - 1) + \omega_0\big) - A \cos\big(\omega (k - 2) + \omega_0\big)\\ \Rightarrow \cos(\omega k + \omega_0) = 2\cos(\omega) \cos\big(\omega (k - 1) + \omega_0\big) - \cos\big(\omega (k - 2) + \omega_0\big)\\ \Rightarrow \cos(\omega k + \omega_0) = \cos\big(\omega - \omega (k - 1) - \omega_0\big) + \cos\big(\omega + \omega (k - 1) + \omega_0\big) - \cos\big(\omega (k - 2) + \omega_0\big)\\ \Rightarrow \cos(\omega k + \omega_0) = \cos\big(\omega - \omega k + \omega - \omega_0\big) + \cos\big(\omega + \omega k - \omega + \omega_0\big) - \cos\big(\omega k - 2\omega + \omega_0\big)\\ \Rightarrow \cos(\omega k + \omega_0) = \cos\big(- \omega k + 2 \omega - \omega_0\big) + \cos\big(\omega k + \omega_0\big) - \cos\big(\omega k - 2\omega + \omega_0\big)\\ \Rightarrow \cos(\omega k + \omega_0) - \cos\big(\omega k - 2 \omega + \omega_0\big) = \cos\big(\omega k + \omega_0\big) - \cos\big(\omega k - 2\omega + \omega_0\big)\\$$

This exact predictor was also presented in Laurent's answer, recognizing that the coefficient for the previous sample is the same in both: $$2 - 4\sin^2(\frac{\omega}{2}) = 2\cos(\omega),$$ where $$\omega = \frac{2\pi h}{T}.$$

Fat32's answer mentions more general all-pole signal models that can also be exactly predicted. A sinusoid with an exponentially decaying envelope is a basic example. Wikipedia's table of common Z-transform pairs hints to that signal–predictor pair, among others:

$$\begin{cases}x[k] = a^n A\cos(\omega k + \omega_0)&\text{(signal)}\\ x[k] = 2a\cos(\omega)x[k - 1] - a^2 x[k - 2]&\text{(exact predictor)}\end{cases}$$

MATLAB's lpc is not exact because it assumes that the data continues beyond its start and end as zero-valued, in order to use an autocorrelation-based method. For your own arbitrary data you can use the following Octave script to find the coefficients that minimize the sum of squared residual error of predicting those data points that are preceded by enough (N or more) data points to enable their prediction:

L = 10; #Data length
N = 3; #Number of prediction coefficients
k = 1:L; #Index variable
x = 123*k.^2 + 456*k + 789 #Test Data (2nd degree polynomial)
m = x(toeplitz(N:L-1, flip(1:N))); #What we predict with
v = x(N+1:L)'; #What we want to predict
c = m\v #Least squares solve prediction coefficients


The above example gives as output the degree 2 polynomial prediction coefficients, the same as in Laurent's answer:

c =

3.0000
-3.0000
1.0000


The sum of squared prediction errors is just numerical error from rounding:

>> sumsq(v - m*c)
ans =    1.4128e-21


N being as small as possible for the given data to make the prediction error virtually zero, the choice of cost function (here least squares) does not matter. With larger N, there would be an extra degree of freedom in the solution that might enable the solver to minimize numerical error by the cost function, allowing its choice to affect the result.

The tail of a pole-zero signal model can also be exactly predicted. Such a signal can be written in form:

$$x[k] = \sum_{n=0}^M b_n \delta[k - n] - \sum_{n=1}^N a_n x[k - n],\quad\text{where }\delta[k] = \begin{cases}1&\text{if }k = 0\\0&\text{otherwise}\end{cases}$$

If $$k > M,$$ then $$\delta[k - n]$$ is always zero and each sample value will only depend on the previous $$N$$ sample values:

$$x[k] = \sum_{n=1}^N -a_n x[k - n],\quad\text{if }k > M$$

with coefficients $$-a_n$$.

For general signals, linear prediction alone is not enough, and the error produced by it must be corrected for in order to exactly produce the desired signal. This is called linear predictive coding. Correction is not added after predicting the complete signal, but to each prediction of a sample before doing the next prediction. This way the prediction on each sample is done based on the exact past signal and not on erroneous past predictions:

$$\begin{array}{rl}\hat x[k] = \sum_{n=1}^N c_n x[k - n]&\quad\text{prediction}\\ e[k] = x[k] - \hat x[k]&\quad\text{prediction error}\\ x[k] = \hat x[k] + e[k] = \sum_{n=1}^N c_n x[k - n] + e[k]&\quad\text{corrected prediction}\end{array}$$

The literature seems to prefer this sign convention in the error. The script in this answer minimizes $$\sum_k e^2[k]$$ for other than the first $$N$$ samples.

Let's consider again signals for which exact prediction is possible. Either a history of $$N$$ samples of $$x[k]$$ must be properly initialized, or alternatively, using the same coefficients, linear predictive coding can be used with non-zero corrections for the first $$N$$ samples, typically with the history of $$x[k]$$ set to zero. After this "warm-up", the rest of $$x[k]$$ will be exactly predicted without auxiliary information or correction.

In addition to Laurent's polynomial signal model example, the following LCCDE (Linear Constant Coefficient Difference Equation) based ARMA (Auto-regressive / Moving-average) signal model also permits exact prediction over its finite number of past samples. Specifically, consider an all-pole signal model of order $$p$$:

$$y[n] + \sum_{k=1}^{p} a_k y[n-k] = x[n]$$ with $$x[n] = \delta[n]$$, and for $$n>0$$ we have (with zero initial conditions on $$y[n]$$)

$$y[n] = - \sum_{k=1}^{p} a_k y[n-k]$$

which shows that the sequence $$y[n]$$ is exactly given by the last $$p$$ values it had, hence perfect linear prediction possible.

• Too bad "prouced" does not seem a valid adjective... I've dug into an old Yule's paper. Do you know of a table of explicit forms for extrapolation coefficients? I'm looking at quantization effects at the present time – Laurent Duval Nov 2 '18 at 10:59
• yes too bad. Let me change it :-) Here this's a deterministic model so Prony's modeling better suits than a Yule approach. (though I have used tthe term ARMA ;-) Quantization effects apply to all dsp systems equally, so not specific to al all-pole model, as given here, but just for any system. So one should consider the numerical consequences of floating point artihmetic. For a very succint treatment, oppenheim DTSP chapter 6 is suggested. – Fat32 Nov 2 '18 at 11:22
• Let me disagree on one point: quantization, since non-linear, does not apply equality when it comes to coding the prediction error (esp. with high range) – Laurent Duval Nov 2 '18 at 11:28
• @LaurentDuval that's true. – Fat32 Nov 2 '18 at 19:33