INTERPOLATION AND THE DISCRETE PAPOULIS-GERCHBERG ALGORITHM

In this paper we analyze the performance of an iterative algorithm, similar to the discrete Papoulis-Gerchberg algorithm, and which can be used to recover missing samples in finite-length records of band-limited data. No assumptions are made regarding the distribution of the missing samples, in contrast with the often studied extrapolation problem, in which the known samples are grouped together. Indeed, it is possible to regard the observed signal as a sampled version of the original one, and to interpret the reconstruction result studied herein as a sampling result. We show that the iterative algorithm converges if the density of the sampling set exceeds a certain minimum value which naturally increases with the bandwidth of the data. We give upper and lower bounds for the error as a function of the number of iterations, together with the signals for which the bounds are attained. Also, we analyze the effect of a relaxation constant present in the algorithm on the spectral radius of the iteration matrix. From this analysis we infer the optimum value of the relaxation constant. We also point out, among all sampling sets with the same density, those for which the convergence rate of the recovery algorithm is maximum or minimum; For low-pass signals it turns out that the best convergence rates result when the distances among the missing samples are a multiple of a certain integer. The worst convergence rates generally occur when the missing samples are contiguous.