Interpolation and the discrete Papoulis-Gerchberg algorithm

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 as a sampling result. The authors 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. They 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, they analyze the effect of a relaxation constant present in the algorithm on the spectral radius of the iteration matrix. From this analysis they infer the optimum value of the relaxation constant. They 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