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

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.

### MSC:

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

### 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) Belfer Graduate School of Science, Yeshiva Univ., New York, 1966, pp. 109 – 125.  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  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.  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. · Zbl 0915.43007  R. J. Duffin and A. C. Schaeffer, A class of nonharmonic Fourier series, Trans. Amer. Math. Soc. 72 (1952), 341 – 366. · Zbl 0049.32401  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  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  Ky Fan, Olga Taussky, and John Todd, Discrete analogs of inequalities of Wirtinger, Monatsh. Math. 59 (1955), 73 – 90. · Zbl 0064.29803  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  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  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  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  Hartmut Führ, Abstract harmonic analysis of continuous wavelet transforms, Lecture Notes in Mathematics, vol. 1863, Springer-Verlag, Berlin, 2005. · Zbl 1060.43002  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  Karlheinz Gröchenig, A discrete theory of irregular sampling, Linear Algebra Appl. 193 (1993), 129 – 150. · Zbl 0795.65099  G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, Cambridge, at the University Press, 1952. 2d ed. · Zbl 0047.05302  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  H. J. Landau, Necessary density conditions for sampling and interpolation of certain entire functions, Acta Math. 117 (1967), 37 – 52. · Zbl 0154.15301  Yurii I. Lyubarskii and Kristian Seip, Weighted Paley-Wiener spaces, J. Amer. Math. Soc. 15 (2002), no. 4, 979 – 1006. · Zbl 1017.46018  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  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  Joaquim Ortega-Cerdà and Kristian Seip, Fourier frames, Ann. of Math. (2) 155 (2002), no. 3, 789 – 806. · Zbl 1015.42023  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  Isaac Pesenson, Sampling of Paley-Wiener functions on stratified groups, J. Fourier Anal. Appl. 4 (1998), no. 3, 271 – 281. · Zbl 0930.43009  Isaac Pesenson, A reconstruction formula for band limited functions in \?$$_{2}$$(\?^{\?}), Proc. Amer. Math. Soc. 127 (1999), no. 12, 3593 – 3600. · Zbl 0998.42024  Isaac Pesenson, A sampling theorem on homogeneous manifolds, Trans. Amer. Math. Soc. 352 (2000), no. 9, 4257 – 4269. · Zbl 0976.43004  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  Isaac Pesenson, Deconvolution of band limited functions on non-compact symmetric spaces, Houston J. Math. 32 (2006), no. 1, 183 – 204. · Zbl 1097.43007  Isaac Pesenson, Band limited functions on quantum graphs, Proc. Amer. Math. Soc. 133 (2005), no. 12, 3647 – 3655. · Zbl 1115.94003  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  Isaac Pesenson, Analysis of band-limited functions on quantum graphs, Appl. Comput. Harmon. Anal. 21 (2006), no. 2, 230 – 244. · Zbl 1103.94011  M. Plancherel, G. Polya, Fonctions entieres et integrales de Fourier multiples, Comment. Math. Helv., 9 (1937), 224-248. · JFM 63.0377.02  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  D. E. Rutherford, Some continuant determinants arising in physics and chemistry, Proc. Roy. Soc. Edinburgh. Sect. A. 62 (1947), 229 – 236. · Zbl 0030.00501  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  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  Hans Triebel, Theory of function spaces. II, Monographs in Mathematics, vol. 84, Birkhäuser Verlag, Basel, 1992. · Zbl 0763.46025  Ahmed I. Zayed, Advances in Shannon’s sampling theory, CRC Press, Boca Raton, FL, 1993. · Zbl 0868.94011
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.