Next: ADAPTIVE FILTERS
Up: Waveform applications of least
Previous: PREDICTION AND SHAPING FILTERS
The uncertainty principle says
that if a time function contains most of its energy
in the timespan ,
then its Fourier transform contains most of its energy
in a bandwidth .
This is not the same as saying
that if we have a sample of a stationary time series
of length ,the best frequency resolution we can hope to attain will be
.The difference lies in the difference between assuming a
function is zero outside the interval in which it is
given and in assuming that it continues ``in a sensible way"
outside the given interval.
If the data sample can be continued ``in a sensible way"
some distance beyond the interval in which it is given,
then the frequency resolution may be considerably
smaller than .A finer resolution depends upon the predictability of the data
off the ends of the sample. If one has a segment of
a stationary series which is short compared to the
autocorrelation of the stationary series,
then the spectral estimation procedure of John P. Burg
will be radically better than any truncated Fourier
transform method. This comes about in physical
problems when one is dealing with resonances which
have decay times that are long compared to the
observation time or when one is looking at a function of
space where each point in space represents another
instrument.
If a spectrum R(Z) is estimated by
where X(Z) is a
polynomial made up from N + 1 known data points,
then the coefficients of R(Z) are computed by
 
(8) 
Notice that r_{0} is calculated from N + 1 terms,
r_{1} from N terms, etc. If N is not large enough,
this will have an undesirable biasing effect.
The biasing is removed if the r_{k} are computed
instead by the formula
 
(9) 
The trouble with using (9) is that data samples
can easily be found for which r_{k} will not be a valid
autocorrelation function. For example,
the spectrum will not be positive at all frequencies,
the solution to Toeplitz equations may blow up, etc.
Burg's approach avoids the endeffect problems of
(8) and the possibility of impossible results
from (9). Instead of estimating the
autocorrelation r_{k} directly from the data he estimates
a minimumphase predictionerror filter directly from the data.
The output of a predictionerror filter
has a white spectrum. (If it did not,
then the color could be used to improve prediction.)
Since the spectrum of the output is the spectrum of the input
times the spectrum of the filter,
the spectrum of the input may be estimated as the inverse
of the spectrum of the predictionerror filter.
As we have seen, narrow spectral peaks are far more
easily represented by a denominator than by a numerator.
Let the given segment of data be denoted by
.Then a twoterm predictionerror filter
(1,a) of the time series x_{t} is given
by the choice of a which minimizes
 
(10) 
Unfortunately,
consideration of a few examples shows that
there exist time series [like (1,2)] for which
a may turn out to be greater than unity.
This is unacceptable because the predictionerror
filter is not minimumphase,
the spectrum is not positive, etc.
Recall that a predictionerror filter defined in the
previous section depends only on the autocorrelation of the
data and not the data per se.
This means that the same filter is
computed from both a time series and
from the (complexconjugate) timereversed time series.
This suggests that the error of forward prediction
(10) be augmented by the error of backward
prediction. That is
 
(11) 
We will later establish that the minimization of
(11) always leads to an a less than unity.
The power spectral estimate associated with this
value of a is
.The value of may be very small if
a turns out very close to the unit circle.
A natural extension of (11) to filters
with more terms would seem to be to minimize
 
(12) 
Unfortunately,
Burg discovered time series for which the computed filter
A(Z) = 1 + a_{1} Z + a_{2} Z^{2} was not minimumphase.
If A(Z) is not minimumphase,
then is not a satisfactory
spectral estimate because R(Z) is to be evaluated
on the unit circle and 1/A(Z) would not be convergent there.
Burg noted that the Levinson recursion always gives
minimumphase filters.
In the Levinson recursion a filter of order 3 is built up
from one of order 2 by
Thus Burg decided that instead of using least squares
to determine a_{1} and a_{2} as in (12),
he would take a to be given from (11)
and then do a leastsquares problem to solve for c.
This would be done in such a way as to ensure that
c comes out less than unity,
which guarantees that A(Z) = 1 + a_{1} Z + a_{2} Z^{2} is
minimumphase. Thus he suggested rewriting (12) as
 

 (13) 
Now the error (13),
which is the sum of the error of forward prediction plus
the error of backward prediction,
is minimized with respect to variation of c.
(In a later chapter we will see fit to call c
a reflection coefficient.)
The quantity a remains fixed by the minimization of (11).
Now let us establish that c is less than unity.
Denote by e_{+} the time series
x_{t} + ax_{t1} which is the error in forward prediction
of x_{t}. Denote by e_{} the time series
of error on backward prediction.
With this, (13) becomes
 

 (14) 
Setting the derivative with respect to equal to zero
 

 (15) 
(One may note that gives the
same result.) That c is always less than unity may
be seen by noting that the length of the vector
is always positive. In particular
 

 
 
 (16) 
If we now redefine e_{+} and e_{} as
 
(17) 
 (18) 
we have the forward and backward prediction errors of the
threeterm filter .One can then return to (14)
and proceed recursively.
As the recursion proceeds e_{+} and e_{} gradually
become unpredictable random numbers.
We have then found a filter A(Z) which filters
X(Z) either forward or backward and the output must
be the inverse of the spectrum of the filter.
In later chapters we will discover a wavepropagation
interpretation of the Burg algorithm.
In a layered medium the parameters c_{k} have the
interpretation of the up and downgoing waves;
and the whole process of calculating a succession of
c_{k} amounts to downward continuing surface
seismograms into the earth, determining an earth model
c_{k} as you go.
EXERCISES:
 Consider the time series with ten points
(1, 1, 1, 1, 1, 1, 1, 1, 1, 1).
Compute C and A up to cubics in Z.
Compare the autocorrelation r_{t} calculated by
Burg's method with R(Z) estimated from the
truncated sample and with R(Z) estimated by intuitively
extending the data sample in time to plus and minus infinity.
 Modify the program of Figure to compute
and include the scale factor V which belongs in the
spectrum.
Next: ADAPTIVE FILTERS
Up: Waveform applications of least
Previous: PREDICTION AND SHAPING FILTERS
Stanford Exploration Project
10/30/1997