Shannon sampling and function reconstruction from point values

Smale, Steve; Zhou, Ding-Xuan

doi:10.1090/S0273-0979-04-01025-0

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-9485(online) ISSN 0273-0979(print)

Shannon sampling and function reconstruction from point values

Authors: Steve Smale and Ding-Xuan Zhou
Journal: Bull. Amer. Math. Soc. 41 (2004), 279-305
MSC (2000): Primary 68T05, 94A20; Secondary 68P05, 42B10
Published electronically: April 13, 2004
MathSciNet review: 2058288
Full-text PDF

[1] Akram Aldroubi, Non-uniform weighted average sampling and reconstruction in shift-invariant and wavelet spaces, Appl. Comput. Harmon. Anal. 13 (2002), no. 2, 151–161. MR 1942749 (2003i:42045), http://dx.doi.org/10.1016/S1063-5203(02)00503-1
[2] Akram Aldroubi and Karlheinz Gröchenig, Nonuniform sampling and reconstruction in shift-invariant spaces, SIAM Rev. 43 (2001), no. 4, 585–620 (electronic). MR 1882684 (2003e:94040), http://dx.doi.org/10.1137/S0036144501386986
[3] N. Aronszajn, Theory of reproducing kernels, Trans. Amer. Math. Soc. 68 (1950), 337–404. MR 0051437 (14,479c), http://dx.doi.org/10.1090/S0002-9947-1950-0051437-7
[4] R. F. Bass and K. Gröchenig, Random sampling of multivariate trigonometric polynomials, preprint, 2003.
[5] G. Bennett, Probability inequalities for the sum of independent random variables, J. Amer. Statis. Assoc. 57 (1962), 33-45.
[6] S. Bochner, Hilbert distances and positive definite functions, Ann. of Math. (2) 42 (1941), 647–656. MR 0005782 (3,206d)
[7] Tony F. Chan, Jianhong Shen, and Luminita Vese, Variational PDE models in image processing, Notices Amer. Math. Soc. 50 (2003), no. 1, 14–26. MR 1948832 (2003m:94008)
[8] Felipe Cucker and Steve Smale, On the mathematical foundations of learning, Bull. Amer. Math. Soc. (N.S.) 39 (2002), no. 1, 1–49 (electronic). MR 1864085 (2003a:68118), http://dx.doi.org/10.1090/S0273-0979-01-00923-5
[9] Felipe Cucker and Steve Smale, Best choices for regularization parameters in learning theory: on the bias-variance problem, Found. Comput. Math. 2 (2002), no. 4, 413–428. MR 1930945 (2003k:68089), http://dx.doi.org/10.1007/s102080010030
[10] Ingrid Daubechies, Ten lectures on wavelets, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 61, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. MR 1162107 (93e:42045)
[11] Jean-Pierre Dedieu, Newton’s method and some complexity aspects of the zero-finding problem, Foundations of computational mathematics (Oxford, 1999) London Math. Soc. Lecture Note Ser., vol. 284, Cambridge Univ. Press, Cambridge, 2001, pp. 45–67. MR 1836614 (2002d:65050)
[12] Luc Devroye, László Györfi, and Gábor Lugosi, A probabilistic theory of pattern recognition, Applications of Mathematics (New York), vol. 31, Springer-Verlag, New York, 1996. MR 1383093 (97d:68196)
[13] Heinz W. Engl, Martin Hanke, and Andreas Neubauer, Regularization of inverse problems, Mathematics and its Applications, vol. 375, Kluwer Academic Publishers Group, Dordrecht, 1996. MR 1408680 (97k:65145)
[14] Theodoros Evgeniou, Massimiliano Pontil, and Tomaso Poggio, Regularization networks and support vector machines, Adv. Comput. Math. 13 (2000), no. 1, 1–50. MR 1759187 (2001f:68053), http://dx.doi.org/10.1023/A:1018946025316
[15] H. G. Feichtinger, Banach convolution algebras of Wiener type, Functions, series, operators, Vol. I, II (Budapest, 1980) Colloq. Math. Soc. János Bolyai, vol. 35, North-Holland, Amsterdam, 1983, pp. 509–524. MR 751019 (85j:43005)
[16] V. V. Ivanov, The theory of approximate methods and their application to the numerical solution of singular integral equations, Noordhoff International Publishing, Leyden, 1976. Translated from the Russian by A. Ideh; Edited by R. S. Anderssen and D. Elliott; Monographs and Textbooks on Mechanics of Solids and Fluids, Mechanics: Analysis, No. 2. MR 0405045 (53 #8841)
[17] Colin McDiarmid, Concentration, Probabilistic methods for algorithmic discrete mathematics, Algorithms Combin., vol. 16, Springer, Berlin, 1998, pp. 195–248. MR 1678578 (2000d:60032), http://dx.doi.org/10.1007/978-3-662-12788-9_6
[18] P. Niyogi, The Informational Complexity of Learning, Kluwer, Dordrecht, 1998.
[19] T. Poggio and S. Smale, The mathematics of learning: dealing with data, Notices Amer. Math. Soc. 50 (2003), 537-544.
[20] David Pollard, Convergence of stochastic processes, Springer Series in Statistics, Springer-Verlag, New York, 1984. MR 762984 (86i:60074)
[21] A. N. Shiryaev, Probability, 2nd ed., Graduate Texts in Mathematics, vol. 95, Springer-Verlag, New York, 1996. Translated from the first (1980) Russian edition by R. P. Boas. MR 1368405 (97c:60003)
[22] Steve Smale and Ding-Xuan Zhou, Estimating the approximation error in learning theory, Anal. Appl. (Singap.) 1 (2003), no. 1, 17–41. MR 1959283 (2003m:68111), http://dx.doi.org/10.1142/S0219530503000089
[23] G. Strang and G. Fix, A Fourier analysis of the finite element variational method, in Constructive Aspects of Functional Analysis, G. Geymonat (ed.), C. I. M. E., 1971, pp. 796-830.
[24] Wenchang Sun and Xingwei Zhou, On the stability of multivariate trigonometric systems, J. Math. Anal. Appl. 235 (1999), no. 1, 159–167. MR 1758675 (2001k:42040), http://dx.doi.org/10.1006/jmaa.1999.6386
[25] Andrey N. Tikhonov and Vasiliy Y. Arsenin, Solutions of ill-posed problems, V. H. Winston & Sons, Washington, D.C.: John Wiley & Sons, New York-Toronto, Ont.-London, 1977. Translated from the Russian; Preface by translation editor Fritz John; Scripta Series in Mathematics. MR 0455365 (56 #13604)
[26] M. Unser, Sampling-50 years after Shannon, Proc. IEEE 88 (2000), 569-587.
[27] Vladimir N. Vapnik, Statistical learning theory, Adaptive and Learning Systems for Signal Processing, Communications, and Control, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR 1641250 (99h:62052)
[28] G. Voronoi, Recherches sur les parallelodres primitives, J. Reine Angew. Math. 134 (1908), 198-287.
[29] Grace Wahba, Spline models for observational data, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR 1045442 (91g:62028)
[30] 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 (81m:42027)
[31] Ahmed I. Zayed, Advances in Shannon’s sampling theory, CRC Press, Boca Raton, FL, 1993. MR 1270907 (95f:94008)
[32] Ding-Xuan Zhou, The covering number in learning theory, J. Complexity 18 (2002), no. 3, 739–767. MR 1928805 (2003k:68095), http://dx.doi.org/10.1006/jcom.2002.0635
[33] Ding-Xuan Zhou, Capacity of reproducing kernel spaces in learning theory, IEEE Trans. Inform. Theory 49 (2003), no. 7, 1743–1752. MR 1985575 (2004c:62095), http://dx.doi.org/10.1109/TIT.2003.813564