Interpolation and the discrete Papoulis-Gerchberg algorithm
- 1 October 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 42 (10), 2596-2606
- https://doi.org/10.1109/78.324726
Abstract
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.Keywords
This publication has 57 references indexed in Scilit:
- A note on the PQ theorem and the extrapolation of signalsIEEE Transactions on Signal Processing, 1993
- Reconstruction of speech signals with lost samplesIEEE Transactions on Signal Processing, 1992
- Recovery of signals from nonuniform samples using iterative methodsIEEE Transactions on Signal Processing, 1991
- On the use of singular value decomposition and decimation in discrete-time band-limited signal extrapolationIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- A unified approach to noniterative linear signal restorationIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- On the Gerchberg - Papoulis algorithmIEEE Transactions on Circuits and Systems, 1983
- Unified Hilbert space approach to iterative least-squares linear signal restorationJournal of the Optical Society of America, 1983
- Iterative time-limited signal restorationIEEE Transactions on Acoustics, Speech, and Signal Processing, 1983
- Constrained iterative restoration algorithmsProceedings of the IEEE, 1981
- Concerning the Recovery of a Bandlimited Signal or Its Spectrum from a Finite SegmentIEEE Transactions on Communications, 1979