Is Linear Prediction ever exact?

Question

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.

Answer 1

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:

• The Theory of Linear Prediction by P. P. Vaidyanathan, or
• chapter 13.6 Linear Prediction and Linear Predictive Coding in Numerical Recipes.

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.

Answer 2

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.

Answer 3

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.