Efficient numerical methods in non-uniform sampling theory (Q1347035)

A new fast algorithm for the reconstruction of band-limited signals from irregular samples is presented. Let a sequence \(0\leq n_1<\cdots< n_r\leq N- 1\) and samples \(s(n_i)\), \(i= 0,\dots, r\) of a discrete band-limited signal \(s\) be given. How can the signal \(s\) be reconstructed fast and efficiently, if the amount of data is large, i.e., \(r\approx 10^3- 10^6\)? First, principal solvability of the reconstruction problem is discussed. In order to make the dimension independent of the number of samples, the problem is reformulated as a Toeplitz system. Now, the dimension of the problem only depends on the length of the band of the signal \(s\), and an efficient Toeplitz solver can be used. The reconstruction can further be improved by the adaptive weights method. This method improves the condition number of the irregular sampling problem, provides estimates for the rate of convergence depending only on the maximal gap size, and gives a useful stopping criterion. Combining the reformulation of the original problem as a Toeplitz system with adaptive weights method and with the conjugate gradient acceleration, a fast and effective reconstruction algorithm is obtained. Finally, efficient implementation of the algorithm is discussed and numerical results are presented. The paper is excellently written and contains a very good description of previous literature as well as a long reference list.