Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type

Gröchenig, Karlheinz

doi:10.1090/S0025-5718-99-01029-7

Irregular sampling, Toeplitz matrices, and the approximation of entire functions of exponential type
HTML articles powered by AMS MathViewer

by Karlheinz Gröchenig PDF

Math. Comp. 68 (1999), 749-765 Request permission

Abstract:

In many applications one seeks to recover an entire function of exponential type from its non-uniformly spaced samples. Whereas the mathematical theory usually addresses the question of when such a function in $L^2(\mathbb {R})$ can be recovered, numerical methods operate with a finite-dimensional model. The numerical reconstruction or approximation of the original function amounts to the solution of a large linear system. We show that the solutions of a particularly efficient discrete model in which the data are fit by trigonometric polynomials converge to the solution of the original infinite-dimensional reconstruction problem. This legitimatizes the numerical computations and explains why the algorithms employed produce reasonable results. The main mathematical result is a new type of approximation theorem for entire functions of exponential type from a finite number of values. From another point of view our approach provides a new method for proving sampling theorems.

References

John J. Benedetto, Frame decompositions, sampling, and uncertainty principle inequalities, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 247–304. MR 1247519
Arne Beurling, The collected works of Arne Beurling. Vol. 1, Contemporary Mathematicians, Birkhäuser Boston, Inc., Boston, MA, 1989. Complex analysis; Edited by L. Carleson, P. Malliavin, J. Neuberger and J. Wermer. MR 1057613
Arne Beurling and Paul Malliavin, On the closure of characters and the zeros of entire functions, Acta Math. 118 (1967), 79–93. MR 209758, DOI 10.1007/BF02392477
P. L. Butzer, W. Splettstösser, and R. L. Stens, The sampling theorem and linear prediction in signal analysis, Jahresber. Deutsch. Math.-Verein. 90 (1988), no. 1, 70. MR 928745
C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
Hans G. Feichtinger and Karlheinz Gröchenig, Theory and practice of irregular sampling, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 305–363. MR 1247520
Hans G. Feichtinger, Karlheinz Gröchenig, and Thomas Strohmer, Efficient numerical methods in non-uniform sampling theory, Numer. Math. 69 (1995), no. 4, 423–440. MR 1314596, DOI 10.1007/s002110050101
Karlheinz Gröchenig, Reconstruction algorithms in irregular sampling, Math. Comp. 59 (1992), no. 199, 181–194. MR 1134729, DOI 10.1090/S0025-5718-1992-1134729-0
Karlheinz Gröchenig, A discrete theory of irregular sampling, Linear Algebra Appl. 193 (1993), 129–150. MR 1240276, DOI 10.1016/0024-3795(93)90275-S
K. Gröchenig. Finite and Infinite-Dimensional Models of Non-Uniform Sampling. Proc. SampTA 97, Aveiro, Portugal, June 1997, pp. 285–290.
C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
S. Jaffard, A density criterion for frames of complex exponentials, Michigan Math. J. 38 (1991), no. 3, 339–348. MR 1116493, DOI 10.1307/mmj/1029004386
H. J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967), 37–52. MR 222554, DOI 10.1007/BF02395039
H. Landau. Extrapolating a band-limited function from its samples taken in a finite interval. IEEE Trans. Information Theory 32(4) (1986), 464–470.
B. S. Pavlov, The basis property of a system of exponentials and the condition of Muckenhoupt, Dokl. Akad. Nauk SSSR 247 (1979), no. 1, 37–40 (Russian). MR 545940
L. Reichel, G. S. Ammar, and W. B. Gragg, Discrete least squares approximation by trigonometric polynomials, Math. Comp. 57 (1991), no. 195, 273–289. MR 1079030, DOI 10.1090/S0025-5718-1991-1079030-8
Kristian Seip, On the connection between exponential bases and certain related sequences in $L^2(-\pi ,\pi )$, J. Funct. Anal. 130 (1995), no. 1, 131–160. MR 1331980, DOI 10.1006/jfan.1995.1066
T. Strohmer. Efficient methods for digital signal and image reconstruction from non-uniform samples. Ph. D. Thesis, University of Vienna, 1993.
Robert M. Young, An introduction to nonharmonic Fourier series, Pure and Applied Mathematics, vol. 93, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. MR 591684
Ahmed I. Zayed, Advances in Shannon’s sampling theory, CRC Press, Boca Raton, FL, 1993. MR 1270907