** Next:** EXAMPLES
** Up:** Balog: Interpolation
** Previous:** THE METHOD

The algorithm suggested by the results of the previous section is to compute from the time Fourier transformed original data , for each frequency , a prediction filter along the *x* axis which is then used at the frequency to solve for the missing data.
I have implemented such an algorithm in the case where *n* is equal to two.
Since the operations are performed in the domain, the data *u*(*t*,*x*) as well as a zero padded version *u*_{pad}(*t*,*x*) of the data, with twice as many time samples as *u*(*t*,*x*), are both Fourier transformed over the time axis.
The one-step forward prediction filters are then computed for all the frequencies from zero to half the Nyquist by solving using Levinson's recursion the following linear system

| |
(15) |

where is the autocorrelation matrix of a frequency slice from and *e* is the minimum prediction error energy.
According to equation (12), for *n*=2, predicts one step ahead the interpolated data . This relation may be thought of as a convolutional operation

| |
(16) |

where and contains the original data interlaced with missing values.
is then separated into an even part and an odd part, respectively and , and into missing and known data, respectively and .
is then obtained from
| |
(17) |

The same computations are performed with the one-step backward prediction filters giving another set of values for the missing data.
The two values found for the missing data in each case are then averaged to give the final result.
The interpolated data is then time inverse fourier transformed to *u*'(*t*,*x*).
It is worth noticing that the backward prediction filters are easily computed from the forward prediction filters and that the zero padding in time of *u*(*t*,*x*) is necessary to avoid any type of filter interpolation in the direction between even frequencies , with *k* even).

** Next:** EXAMPLES
** Up:** Balog: Interpolation
** Previous:** THE METHOD
Stanford Exploration Project

12/18/1997