A fast algorithm for extrapolation of discrete-time periodic band-limited signals

Abstract

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-discrete extrapolation, which required computation of a large pseudo-inverse. The procedure is highly parallelizable, 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.