Sampling, filtering and sparse approximations on combinatorial graphs. (English) Zbl 1218.42021

This paper firstly proves a Poincaré and Plancherel type inequality on graphs. Then by combining this inequality with the ideas of Duffin and Shaeffer’s theory, the authors give a sampling theorem. Finally with the filtering procedure, the authors obtain sparse approximations to functions in \(L_2(G)\).


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


[1] Akhiezer, J.: Theory of Approximation. Ungar, New York (1956) · Zbl 0072.43701
[2] Belkin, M., Niyogi, P.: Towards a theoretical foundation for Laplacian-based manifold methods. In: Learning Theory. Lecture Notes in Comput. Sci., vol. 3559, pp. 486–500. Springer, Berlin (2005) · Zbl 1137.68521
[3] Belkin, M., Matveeva, I., Niyogi, P.: Regularization and semi-supervised learning on large graphs. In: Learning Theory. Lecture Notes in Comput. Sci., vol. 3120, pp. 624–638. Springer, Berlin (2004) · Zbl 1078.68685
[4] Birman, M., Solomyak, M.: Spectral Theory of Selfadjoint Operators in Hilbert Space. Reidel, Dordrecht (1987) · Zbl 0744.47017
[5] Bremer, J.C., Coifman, R.R., Maggioni, M., Szlam, A.D.: Diffusion wavelet packets. Appl. Comput. Harmon. Anal. 21(1), 95–112 (2006) · Zbl 1093.42021
[6] Chung, F.R.K.: Spectral Graph Theory. CBMS, vol. 92. AMS, Providence (1994)
[7] Coifman, R.R., Maggioni, M.: Diffusion wavelets. Appl. Comput. Harmon. Anal. 21(1), 53–94 (2006) · Zbl 1095.94007
[8] Coifman, R.R., Maggioni, M.: Diffusion wavelets for multiscale analysis on graphs and manifolds. In: Wavelets and Splines: Athens 2005. Mod. Methods Math., pp. 164–188. Nashboro Press, Brentwood (2006) · Zbl 1099.65145
[9] Duffin, R., Schaeffer, A.: A class of nonharmonic Fourier series. Trans. AMS 72, 341–366 (1952) · Zbl 0049.32401
[10] Frazier, M.W., Torres, R.: The sampling theorem, {\(\phi\)}-transform, and Shannon wavelets for \(\mathbb{R}\), \(\mathbb{Z}\), \(\mathbb{T}\) , and \(\mathbb{Z}\) N . In: Wavelets: Mathematics and Applications. Stud. Adv. Math., pp. 221–246. CRC, Boca Raton (1994)
[11] Gröchenig, K.: A discrete theory of irregular sampling. Linear Algebra Its Appl. 193, 129–150 (1993) · Zbl 0795.65099
[12] Herman, G.T., Kuba, A.: Discrete Tomography, Foundations, Algorithms, and Applications. Birkhauser, Basel (1999) · Zbl 0946.00014
[13] Maggioni, M., Mhaskar, H.N.: Diffusion polynomial frames on metric measure spaces. Appl. Comput. Harmon. Anal. 24(3), 329–353 (2008) · Zbl 1242.42027
[14] Magyar, A., Stein, E.M., Wainger, S.: Discrete analogues in harmonic analysis: spherical averages. Ann. Math. (2) 155(1), 189–208 (2002) · Zbl 1036.42018
[15] Mahadevan, S.: Representation Discovery Using Harmonic Analysis. Synthesis Lectures on Artificial Intelligence and Machine Learning. Morgan and Claypool, San Rafael (2008) · Zbl 1209.68403
[16] Nikolskii, S.M.: Approximation of Functions of Several Variables and Imbedding Theorems. Springer, Berlin (1975)
[17] Peinecke, N., Walter, F., Reiter, M.: Laplace spectra as fingerprints for image recognition. Comput.-Aided Des. 39, 460–476 (2007) · Zbl 05861414
[18] Pesenson, I.: A sampling theorem on homogeneous manifolds. Trans. AMS 352(9), 4257–4270 (2000) · Zbl 0976.43004
[19] Pesenson, I.: Sampling of Band limited vectors. J. Fourier Anal. Appl. 7(1), 93–100 (2001) · Zbl 0998.42025
[20] Pesenson, I.: Sampling in Paley-Wiener spaces on combinatorial graphs. Trans. Am. Math. Soc. 360(10), 5603–5627 (2008) · Zbl 1165.42010
[21] Pesenson, I.: Variational splines and Paley-Wiener spaces on combinatorial graphs. Constr. Approx. 29(1), 1–20 (2009) · Zbl 1180.42026
[22] Pesenson, I.: Removable sets and eigenvalue and eigenfunction approximations on finite combinatorial graphs. Appl. Comput. Harmon. Anal. (on line) · Zbl 1283.42054
[23] Pesenson, I., Pesenson, M.: Eigenmaps and minimal and bandlimited immersions of graphs into Euclidean spaces. J. Math. Anal. Appl. (on line) · Zbl 1217.05154
[24] Pesenson, M., Carey, S., Pesenson, I., et al.: Astronomical Applications of Image Inpainting and Data Dimension Reduction. Astronomical Data Analysis, Software and Systems, XVIII, Quebec (2008) · Zbl 1256.43004
[25] Pesenson, M., Pesenson, I., Carey, S.: More to astronomical images than meets the eye: data dimension reduction for efficient data organization, retrieval and advanced visualization and analysis of large multitemporal/multispectral data sets. In: 213th American Astronomical Society Meeting, Long Beach, January 2009
[26] Reiter, M., Walter, F., Peinecke, N.: Laplace-Beltrami spectra as ”Shape-DNA” for surfaces and solids. Comput.-Aided Des. 38, 342–366 (2006) · Zbl 05861321
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.