Sampling in Paley-Wiener spaces on combinatorial graphs

Pesenson, Isaac

doi:10.1090/S0002-9947-08-04511-X

Sampling in Paley-Wiener spaces on combinatorial graphs
HTML articles powered by AMS MathViewer

by Isaac Pesenson PDF

Trans. Amer. Math. Soc. 360 (2008), 5603-5627 Request permission

Erratum: Trans. Amer. Math. Soc. 361 (2009), 3951-3951.

Abstract:

A notion of Paley-Wiener spaces on combinatorial graphs is introduced. It is shown that functions from some of these spaces are uniquely determined by their values on some sets of vertices which are called the uniqueness sets. Such uniqueness sets are described in terms of Poincare-Wirtinger-type inequalities. A reconstruction algorithm of Paley-Wiener functions from uniqueness sets which uses the idea of frames in Hilbert spaces is developed. Special consideration is given to the $n$-dimensional lattice, homogeneous trees, and eigenvalue and eigenfunction problems on finite graphs.

References

Arne Beurling, Local harmonic analysis with some applications to differential operators, Some Recent Advances in the Basic Sciences, Vol. 1 (Proc. Annual Sci. Conf., Belfer Grad. School Sci., Yeshiva Univ., New York, 1962-1964) Yeshiva Univ., Belfer Graduate School of Science, New York, 1966, pp. 109–125. MR 0427956
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
M. Sh. Birman and M. Z. Solomjak, Spectral theory of selfadjoint operators in Hilbert space, Mathematics and its Applications (Soviet Series), D. Reidel Publishing Co., Dordrecht, 1987. Translated from the 1980 Russian original by S. Khrushchëv and V. Peller. MR 1192782
F. R. K. Chung, Spectral Graph Theory, CBMS 92, AMS, 1994.
Michael Cowling, Stefano Meda, and Alberto G. Setti, An overview of harmonic analysis on the group of isometries of a homogeneous tree, Exposition. Math. 16 (1998), no. 5, 385–423. MR 1656839
R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952), 341–366. MR 47179, DOI 10.1090/S0002-9947-1952-0047179-6
Mitsuhiko Ebata, Masaaki Eguchi, Shin Koizumi, and Keisaku Kumahara, On sampling formulas on symmetric spaces, J. Fourier Anal. Appl. 12 (2006), no. 1, 1–15. MR 2215673, DOI 10.1007/s00041-005-4014-0
Mitsuhiko Ebata, Masaaki Eguchi, Shin Koizumi, and Keisaku Kumahara, Analogues of sampling theorems for some homogeneous spaces, Hiroshima Math. J. 36 (2006), no. 1, 125–140. MR 2213647
Ky Fan, Olga Taussky, and John Todd, Discrete analogs of inequalities of Wirtinger, Monatsh. Math. 59 (1955), 73–90. MR 70676, DOI 10.1007/BF01302991
Hans Feichtinger and Isaac Pesenson, Recovery of band-limited functions on manifolds by an iterative algorithm, Wavelets, frames and operator theory, Contemp. Math., vol. 345, Amer. Math. Soc., Providence, RI, 2004, pp. 137–152. MR 2066825, DOI 10.1090/conm/345/06244
Hans Feichtinger and Isaac Pesenson, A reconstruction method for band-limited signals on the hyperbolic plane, Sampl. Theory Signal Image Process. 4 (2005), no. 2, 107–119. MR 2138377
Alessandro Figà-Talamanca and Claudio Nebbia, Harmonic analysis and representation theory for groups acting on homogeneous trees, London Mathematical Society Lecture Note Series, vol. 162, Cambridge University Press, Cambridge, 1991. MR 1152801, DOI 10.1017/CBO9780511662324
Michael Frazier and Rodolfo Torres, The sampling theorem, $\phi$-transform, and Shannon wavelets for $\textbf {R}$, $\textbf {Z}$, $\textbf {T}$ and $Z_N$, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 221–245. MR 1247518
Hartmut Führ, Abstract harmonic analysis of continuous wavelet transforms, Lecture Notes in Mathematics, vol. 1863, Springer-Verlag, Berlin, 2005. MR 2130226, DOI 10.1007/b104912
H. Führ and K. Gröchenig, Sampling theorems on locally compact groups from oscillation estimates, Math. Z. 255 (2007), no. 1, 177–194. MR 2262727, DOI 10.1007/s00209-006-0019-x
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
G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2d ed. MR 0046395
Gabor T. Herman and Attila Kuba (eds.), Discrete tomography, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 1999. Foundations, algorithms, and applications. MR 1722457, DOI 10.1007/978-1-4612-1568-4
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
Yurii I. Lyubarskii and Kristian Seip, Weighted Paley-Wiener spaces, J. Amer. Math. Soc. 15 (2002), no. 4, 979–1006. MR 1915824, DOI 10.1090/S0894-0347-02-00397-1
A. Magyar, E. M. Stein, and S. Wainger, Discrete analogues in harmonic analysis: spherical averages, Ann. of Math. (2) 155 (2002), no. 1, 189–208. MR 1888798, DOI 10.2307/3062154
Bojan Mohar, The Laplacian spectrum of graphs, Graph theory, combinatorics, and applications. Vol. 2 (Kalamazoo, MI, 1988) Wiley-Intersci. Publ., Wiley, New York, 1991, pp. 871–898. MR 1170831
Joaquim Ortega-Cerdà and Kristian Seip, Fourier frames, Ann. of Math. (2) 155 (2002), no. 3, 789–806. MR 1923965, DOI 10.2307/3062132
Raymond E. A. C. Paley and Norbert Wiener, Fourier transforms in the complex domain, American Mathematical Society Colloquium Publications, vol. 19, American Mathematical Society, Providence, RI, 1987. Reprint of the 1934 original. MR 1451142, DOI 10.1090/coll/019
Isaac Pesenson, Sampling of Paley-Wiener functions on stratified groups, J. Fourier Anal. Appl. 4 (1998), no. 3, 271–281. MR 1650917, DOI 10.1007/BF02476027
Isaac Pesenson, A reconstruction formula for band limited functions in $L_2(\textbf {R}^d)$, Proc. Amer. Math. Soc. 127 (1999), no. 12, 3593–3600. MR 1610773, DOI 10.1090/S0002-9939-99-04938-2
Isaac Pesenson, A sampling theorem on homogeneous manifolds, Trans. Amer. Math. Soc. 352 (2000), no. 9, 4257–4269. MR 1707201, DOI 10.1090/S0002-9947-00-02592-7
Isaac Pesenson, Poincaré-type inequalities and reconstruction of Paley-Wiener functions on manifolds, J. Geom. Anal. 14 (2004), no. 1, 101–121. MR 2030577, DOI 10.1007/BF02921868
Isaac Pesenson, Deconvolution of band limited functions on non-compact symmetric spaces, Houston J. Math. 32 (2006), no. 1, 183–204. MR 2202361
Isaac Pesenson, Band limited functions on quantum graphs, Proc. Amer. Math. Soc. 133 (2005), no. 12, 3647–3655. MR 2163603, DOI 10.1090/S0002-9939-05-07981-5
Isaac Pesenson, Frames for spaces of Paley-Wiener functions on Riemannian manifolds, Integral geometry and tomography, Contemp. Math., vol. 405, Amer. Math. Soc., Providence, RI, 2006, pp. 135–148. MR 2239176, DOI 10.1090/conm/405/07618
Isaac Pesenson, Analysis of band-limited functions on quantum graphs, Appl. Comput. Harmon. Anal. 21 (2006), no. 2, 230–244. MR 2259780, DOI 10.1016/j.acha.2006.02.003
M. Plancherel, G. Polya, Fonctions entieres et integrales de Fourier multiples, Comment. Math. Helv., 9 (1937), 224-248.
M. Plancherel and G. Pólya, Fonctions entières et intégrales de fourier multiples, Comment. Math. Helv. 10 (1937), no. 1, 110–163 (French). MR 1509570, DOI 10.1007/BF01214286
D. E. Rutherford, Some continuant determinants arising in physics and chemistry, Proc. Roy. Soc. Edinburgh Sect. A 62 (1947), 229–236. MR 20070
Steve Smale and Ding-Xuan Zhou, Shannon sampling. II. Connections to learning theory, Appl. Comput. Harmon. Anal. 19 (2005), no. 3, 285–302. MR 2186447, DOI 10.1016/j.acha.2005.03.001
Steve Smale and Ding-Xuan Zhou, Shannon sampling and function reconstruction from point values, Bull. Amer. Math. Soc. (N.S.) 41 (2004), no. 3, 279–305. MR 2058288, DOI 10.1090/S0273-0979-04-01025-0
Hans Triebel, Theory of function spaces. II, Monographs in Mathematics, vol. 84, Birkhäuser Verlag, Basel, 1992. MR 1163193, DOI 10.1007/978-3-0346-0419-2
Ahmed I. Zayed, Advances in Shannon’s sampling theory, CRC Press, Boca Raton, FL, 1993. MR 1270907