EFFICIENT NUMERICAL-METHODS IN NONUNIFORM SAMPLING THEORY

We present a new ''second generation'' reconstruction algorithm for ir regular sampling, i.e. for the problem of recovering a band-limited fu nction from its non-uniformly sampled values, The efficient new method is a combination of the adaptive weights method which was developed b y the two first named authors and the method of conjugate gradients fo r the solution of positive definite linear systems. The choice of ''ad aptive weights'' can be seen as a simple but very efficient method of preconditioning. Further substantial acceleration is achieved by utili zing the Toeplitz-type structure of the system matrix. This new algori thm can handle problems of much larger dimension and condition number than have been accessible so far. Furthermore, if some gaps between sa mples are large, then the algorithm can still be used as a very effici ent extrapolation method across the gaps.