Efficient numerical methods in non-uniform sampling theory
type: Item
instance of: scholarly article
title: Efficient numerical methods in non-uniform sampling theory
zbMATH Open document ID: 0837.65148
author: Karlheinz Gröchenig
author: Thomas Strohmer
author: H. G. Feichtinger
published in: Numerische Mathematik
publication date: 1996-05-21T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65T40
Mathematics Subject Classification ID: 42A15
Mathematics Subject Classification ID: 65F10
zbMATH DE Number: 739403
zbMATH Keywords: adaptive weights
zbMATH Keywords: extrapolation
zbMATH Keywords: fast algorithm
zbMATH Keywords: reconstruction of band- limited signals
zbMATH Keywords: irregular samples
zbMATH Keywords: Toeplitz system
zbMATH Keywords: condition number
zbMATH Keywords: convergence
zbMATH Keywords: stopping criteria
zbMATH Keywords: conjugate gradient acceleration
zbMATH Keywords: numerical results
reviewed by: Gerlind Plonka
MaRDI profile type: Publication
full work available at URL: s002110050101
OpenAlex ID: W2154625249
DOI: 10.1007/S002110050101
description: scientific article; zbMATH DE number 739403