Sampling in Paley-Wiener spaces on combinatorial graphs. (English) Zbl 1165.42010

Pesenson, Isaac

Trans. Am. Math. Soc. 360, No. 10, 5603-5627 (2008); erratum ibid. 361, No. 7, 3951-3951 (2009).

A function \(f\in L_2(\mathbb{R})\) is called \(\omega\)-bandlimited if its Fourier-transform \(\hat{f}(t)=\int_{-\infty}^{\infty}f(x)e^{-2\pi ixt}dx\) has support in \([-\omega,\omega]\). These functions are called Paley-Wiener functions and form the so-called Paley-Wiener class \(PW_\omega(\mathbb{R})\).
The classical sampling theorem says that such functions can be completely determined by their values at points \(j/2\omega\) (\(j\in\mathbb{Z}\)). It is also possible to consider irregular sampling at points \(\{x_j\}\) (under some conditions on the function).
The author introduces a framework to develop a sampling theory of bandlimited (or Paley-Wiener) functions on combinatorial graphs. More precisely, it is shown that bandlimited functions can be reconstructed by their values on certain subgraphs. The main theorem is the following.
For a given \(\omega_{\min}<\omega<\sqrt{1+\frac{1}{d(G)}}\) consider a set of vertices \(S=\cup S_j\) with the following properties:
1) for every \(S_j\subset V(G)\) the inequality \(\frac{1}{\lambda_1(\Gamma(S_j))}<1/\omega\) holds, where \(\lambda_1(\Gamma(S_j))\) is the first positive eigenvalue of the graph \(\Gamma(S_j)\),
2) the sets \(S_j\cup \{v\in V(G)\setminus S_j:\exists\{u,v\}\in E(G),u\in S_j\}\) are disjoint.
Then the set \(U=V(G)\setminus S\) is a uniqueness set for the space \(PW_\omega(G)\) (uniqueness means that if two functions coincide on this, then they coincide on the whole \(V(G)\)).
Moreover, there exists a frame of functions \(\{\Theta_u\}_{u\in U}\) in the space \(PW_\omega(G)\) such that the following reconstruction formula holds for all \(f\in PW_\omega(G)\): \[ f(v)=\sum_{u\in U}f(u)\Theta_u(v)\quad(v\in V(G)). \] Detailed consideration is given to the \(n\)-dimensional lattice \(\mathbb{Z}^n\), homogeneous trees and finite graphs.

Reviewer: István Mező (Debrecen)

MSC:

42C99	Nontrigonometric harmonic analysis
05C99	Graph theory
94A20	Sampling theory in information and communication theory
94A12	Signal theory (characterization, reconstruction, filtering, etc.)

Keywords:

combinatorial graph; combinatorial Laplace operator; discrete Paley-Wiener spaces; Shannon sampling; discrete Plancherel-Polya and Poincaré inequalities

References:

[1]	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) Belfer Graduate School of Science, Yeshiva Univ., New York, 1966, pp. 109 – 125.
[2]	Arne Beurling and Paul Malliavin, On the closure of characters and the zeros of entire functions, Acta Math. 118 (1967), 79 – 93. · Zbl 0171.11901
[3]	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.
[4]	F. R. K. Chung, Spectral Graph Theory, CBMS 92, AMS, 1994.
[5]	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. · Zbl 0915.43007
[6]	R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952), 341 – 366. · Zbl 0049.32401
[7]	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. · Zbl 1092.43004
[8]	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. · Zbl 1104.43004
[9]	Ky Fan, Olga Taussky, and John Todd, Discrete analogs of inequalities of Wirtinger, Monatsh. Math. 59 (1955), 73 – 90. · Zbl 0064.29803
[10]	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. · Zbl 1077.42021
[11]	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. · Zbl 1137.94314
[12]	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. · Zbl 1154.22301
[13]	Michael Frazier and Rodolfo Torres, The sampling theorem, \?-transform, and Shannon wavelets for \?, \?, \? and \?_{\?}, Wavelets: mathematics and applications, Stud. Adv. Math., CRC, Boca Raton, FL, 1994, pp. 221 – 245. · Zbl 0882.42027
[14]	Hartmut Führ, Abstract harmonic analysis of continuous wavelet transforms, Lecture Notes in Mathematics, vol. 1863, Springer-Verlag, Berlin, 2005. · Zbl 1060.43002
[15]	H. Führ and K. Gröchenig, Sampling theorems on locally compact groups from oscillation estimates, Math. Z. 255 (2007), no. 1, 177 – 194. · Zbl 1132.43005
[16]	Karlheinz Gröchenig, A discrete theory of irregular sampling, Linear Algebra Appl. 193 (1993), 129 – 150. · Zbl 0795.65099
[17]	G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2d ed. · Zbl 0047.05302
[18]	Gabor T. Herman and Attila Kuba , Discrete tomography, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 1999. Foundations, algorithms, and applications. · Zbl 0959.92014
[19]	H. J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967), 37 – 52. · Zbl 0154.15301
[20]	Yurii I. Lyubarskii and Kristian Seip, Weighted Paley-Wiener spaces, J. Amer. Math. Soc. 15 (2002), no. 4, 979 – 1006. · Zbl 1017.46018
[21]	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. · Zbl 1036.42018
[22]	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. · Zbl 0840.05059
[23]	Joaquim Ortega-Cerdà and Kristian Seip, Fourier frames, Ann. of Math. (2) 155 (2002), no. 3, 789 – 806. · Zbl 1015.42023
[24]	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. · Zbl 0123.30104
[25]	Isaac Pesenson, Sampling of Paley-Wiener functions on stratified groups, J. Fourier Anal. Appl. 4 (1998), no. 3, 271 – 281. · Zbl 0930.43009
[26]	Isaac Pesenson, A reconstruction formula for band limited functions in \?\(_{2}\)(\?^{\?}), Proc. Amer. Math. Soc. 127 (1999), no. 12, 3593 – 3600. · Zbl 0998.42024
[27]	Isaac Pesenson, A sampling theorem on homogeneous manifolds, Trans. Amer. Math. Soc. 352 (2000), no. 9, 4257 – 4269. · Zbl 0976.43004
[28]	Isaac Pesenson, Poincaré-type inequalities and reconstruction of Paley-Wiener functions on manifolds, J. Geom. Anal. 14 (2004), no. 1, 101 – 121. · Zbl 1080.42024
[29]	Isaac Pesenson, Deconvolution of band limited functions on non-compact symmetric spaces, Houston J. Math. 32 (2006), no. 1, 183 – 204. · Zbl 1097.43007
[30]	Isaac Pesenson, Band limited functions on quantum graphs, Proc. Amer. Math. Soc. 133 (2005), no. 12, 3647 – 3655. · Zbl 1115.94003
[31]	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. · Zbl 1107.43010
[32]	Isaac Pesenson, Analysis of band-limited functions on quantum graphs, Appl. Comput. Harmon. Anal. 21 (2006), no. 2, 230 – 244. · Zbl 1103.94011
[33]	M. Plancherel, G. Polya, Fonctions entieres et integrales de Fourier multiples, Comment. Math. Helv., 9 (1937), 224-248. · JFM 63.0377.02
[34]	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). · Zbl 0018.15204
[35]	D. E. Rutherford, Some continuant determinants arising in physics and chemistry, Proc. Roy. Soc. Edinburgh. Sect. A. 62 (1947), 229 – 236. · Zbl 0030.00501
[36]	Steve Smale and Ding-Xuan Zhou, Shannon sampling. II. Connections to learning theory, Appl. Comput. Harmon. Anal. 19 (2005), no. 3, 285 – 302. · Zbl 1107.94008
[37]	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. · Zbl 1107.94007
[38]	Hans Triebel, Theory of function spaces. II, Monographs in Mathematics, vol. 84, Birkhäuser Verlag, Basel, 1992. · Zbl 0763.46025
[39]	Ahmed I. Zayed, Advances in Shannon’s sampling theory, CRC Press, Boca Raton, FL, 1993. · Zbl 0868.94011