A Fast Algorithm for Extrapolation of Discrete-Time Periodic Band-Limited Signals
We present a fast algorithm for exact extrapolation of a discrete-time and periodic band-limited signal from its values in an interval having the same length as the band-width of the signal. Here band-width is the number of non-zero values in one period of the discrete Fourier transform of the signal. Applications to problems in which the number of given values is unequal to the band-width are also given. The procedure is a simple autoregression on the time-domain values of the signal, and is much simpler than previous algorithms for discrete~tiscrete extrapolation, which required computation of a large pseudo-inverse. The procedure is highly paralle- lizable, and the computational savings are especially significant for multidimensional signal extrapolation. Numerical examples for 1 -D and 2-D extrapolation demonstrate ( 1 ) that the procedure works perfectly in the absence of noise, and (2) that it works well in the presence of band-limited noise. In the presence of wide-band noise the procedure breaks down, due to ill-posedness of the problem; some regularization techniques are proposed.