Random sampling of bandlimited signals on graphs. (English) Zbl 1391.94367

Puy, Gilles; Tremblay, Nicolas; Gribonval, Rémi; Vandergheynst, Pierre

Appl. Comput. Harmon. Anal. 44, No. 2, 446-475 (2018).

Summary: We study the problem of sampling \(k\)-bandlimited signals on graphs. We propose two sampling strategies that consist in selecting a small subset of nodes at random. The first strategy is non-adaptive, i.e., independent of the graph structure, and its performance depends on a parameter called the graph coherence. On the contrary, the second strategy is adaptive but yields optimal results. Indeed, no more than \(O(k\log (k))\) measurements are sufficient to ensure an accurate and stable recovery of all \(k\)-bandlimited signals. This second strategy is based on a careful choice of the sampling distribution, which can be estimated quickly. Then, we propose a computationally efficient decoder to reconstruct \(k\)-bandlimited signals from their samples. We prove that it yields accurate reconstructions and that it is also stable to noise. Finally, we conduct several experiments to test these techniques.

MSC:

94A12	Signal theory (characterization, reconstruction, filtering, etc.)
94A20	Sampling theory in information and communication theory
05C90	Applications of graph theory
94C15	Applications of graph theory to circuits and networks

Keywords:

graph signal processing; sampling; compressed sensing

Software:

PyGSP; GSPBOX

References:

[1]	Newman, M., Networks: an introduction, (2010), Oxford University Press
[2]	Shuman, D.; Narang, S.; Frossard, P.; Ortega, A.; Vandergheynst, P., The emerging field of signal processing on graphs: extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Process. Mag., 30, 3, 83-98, (2013)
[3]	Sandryhaila, A.; Moura, J., Big data analysis with signal processing on graphs: representation and processing of massive data sets with irregular structure, IEEE Signal Process. Mag., 31, 5, 80-90, (2014)
[4]	Unser, M., Sampling-50 years after Shannon, Proc. IEEE, 88, 4, 569-587, (2000) · Zbl 1404.94028
[5]	Shannon, C., Communication in the presence of noise, Proc. IRE, 37, 1, 10-21, (1949)
[6]	McEwen, J. D.; Wiaux, Y., A novel sampling theorem on the sphere, IEEE Trans. Signal Process., 59, 12, 5876-5887, (2011) · Zbl 1393.94696
[7]	Gröchenig, K., Reconstruction algorithms in irregular sampling, Math. Comp., 59, 199, 181-194, (1992) · Zbl 0756.65159
[8]	Benedetto, J. J., Irregular sampling and frames, wavelets: a tutorial, Theory Appl., 2, 445-507, (1992) · Zbl 0777.42009
[9]	Candès, E. J., Compressive sampling, (Proceedings of the International Congress of Mathematicians, vol. 3, Madrid, Spain, (2006)), 1433-1452 · Zbl 1130.94013
[10]	Chen, S.; Varma, R.; Sandryhaila, A.; Kovacevic, J., Discrete signal processing on graphs: sampling theory, IEEE Trans. Signal Process., 99, 1, (2015)
[11]	Anis, A.; Gadde, A.; Ortega, A., Towards a sampling theorem for signals on arbitrary graphs, (2014 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, (2014)), 3864-3868
[12]	Narang, S.; Ortega, A., Compact support biorthogonal wavelet filterbanks for arbitrary undirected graphs, IEEE Trans. Signal Process., 61, 19, 4673-4685, (2013) · Zbl 1393.94978
[13]	Pesenson, I., Sampling in Paley-Wiener spaces on combinatorial graphs, Trans. Amer. Math. Soc., 360, 10, 5603-5627, (2008) · Zbl 1165.42010
[14]	Pesenson, I. Z.; Pesenson, M. Z., Sampling, filtering and sparse approximations on combinatorial graphs, J. Fourier Anal. Appl., 16, 6, 921-942, (2010) · Zbl 1218.42021
[15]	Anis, A.; Gamal, A. E.; Avestimehr, S.; Ortega, A., Asymptotic justification of bandlimited interpolation of graph signals for semi-supervised learning, (2015 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, (2015)), 5461-5465
[16]	Chen, S.; Sandryhaila, A.; Kovacevic, J., Sampling theory for graph signals, (2015 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, (2015)), 3392-3396
[17]	Anis, A.; Gadde, A.; Ortega, A., Efficient sampling set selection for bandlimited graph signals using graph spectral proxies, IEEE Trans. Signal Process., 99, 1, (2016) · Zbl 1414.94853
[18]	Nguyen, H.; Do, M., Downsampling of signals on graphs via maximum spanning trees, IEEE Trans. Signal Process., 63, 1, 182-191, (2015) · Zbl 1394.94830
[19]	Shuman, D. I.; Faraji, M. J.; Vandergheynst, P., A multiscale pyramid transform for graph signals, IEEE Trans. Signal Process., 64, 8, 2119-2134, (2016) · Zbl 1414.94566
[20]	Irion, J.; Naoki, S., Applied and computational harmonic analysis on graphs and networks, (Proc. SPIE Conf. WAVELET XVI, vol. 9597, (2015))
[21]	Tremblay, N.; Borgnat, P., Subgraph-based filterbanks for graph signals, IEEE Trans. Signal Process., 99, 1, (2016) · Zbl 1414.94625
[22]	Agaskar, A.; Lu, Y., A spectral graph uncertainty principle, IEEE Trans. Inform. Theory, 59, 7, 4338-4356, (2013) · Zbl 1364.94103
[23]	Rabbat, M.; Gripon, V., Towards a spectral characterization of signals supported on small-world networks, (2014 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, (2014)), 4793-4797
[24]	Nakatsukasa, Y.; Saito, N.; Woei, E., Mysteries around the graph Laplacian eigenvalue 4, Linear Algebra Appl., 438, 8, 3231-3246, (2013) · Zbl 1262.05102
[25]	Puy, G.; Vandergheynst, P.; Wiaux, Y., On variable density compressive sampling, IEEE Signal Process. Lett., 18, 10, 595-598, (2011)
[26]	Krahmer, F.; Ward, R., Stable and robust sampling strategies for compressive imaging, IEEE Trans. Image Process., 23, 2, 612-622, (2013) · Zbl 1374.94181
[27]	Adcock, B.; Hansen, A. C.; Poon, C.; Roman, B., Breaking the coherence barrier: a new theory for compressed sensing · Zbl 1410.94030
[28]	Chen, S.; Varma, R.; Singh, A.; Kovacević, J., Signal recovery on graphs: random versus experimentally designed sampling, (2015 International Conference on Sampling Theory and Applications, SampTA, (2015)), 337-341
[29]	Chung, F., Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, (1997), Amer. Mathematical Society
[30]	Candes, E.; Romberg, J., Sparsity and incoherence in compressive sampling, Inverse Probl., 23, 3, 969-985, (2007) · Zbl 1120.94005
[31]	Foucart, S.; Rauhut, H., A mathematical introduction to compressive sensing, applied and numerical harmonic analysis, (2013), Springer New York
[32]	Lustig, M.; Donoho, D.; Pauly, J. M., Sparse MRI: the application of compressed sensing for rapid MR imaging, Magn. Reson. Med., 58, 6, 1182-1195, (2007)
[33]	Chauffert, N.; Ciuciu, P.; Weiss, P., Variable density compressed sensing in MRI. theoretical vs heuristic sampling strategies, (Proc. IEEE Int. Symp. on Biomedical Imaging, (2013)), 298-301
[34]	Boyer, C.; Bigot, J.; Weiss, P., Compressed sensing with structured sparsity and structured acquisition · Zbl 1454.94010
[35]	Bigot, J.; Boyer, C.; Weiss, P., An analysis of block sampling strategies in compressed sensing, IEEE Trans. Inform. Theory, 62, 4, 2125-2139, (2016) · Zbl 1359.94063
[36]	Drineas, P.; Ismail, M. M.; Mahoney, M. W.; Woodruff, D. P., Fast approximation of matrix coherence and statistical leverage, J. Mach. Learn. Res., 13, 3475-3506, (2012) · Zbl 1437.65030
[37]	Drineas, P.; Mahoney, M. W.; Muthukrishnan, S., Sampling algorithms for l2 regression and applications, (Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA’06, (2006)), 1127-1136 · Zbl 1194.62010
[38]	Mahoney, M. W., Randomized algorithms for matrices and data, Found. Trends Mach. Learn., 3, 2, 123-224, (2011) · Zbl 1232.68173
[39]	S. Chen, R. Varma, A. Singh, J. Kovacevic, A statistical perspective of sampling scores for linear regression, 2016, submitted for publication, arXiv:1507.05870.
[40]	Drineas, P.; Mahoney, M. W.; Muthukrishnan, S., Relative-error cur matrix decompositions, SIAM J. Matrix Anal. Appl., 30, 2, 844-881, (2008) · Zbl 1183.68738
[41]	Gittens, A.; Mahoney, M., Revisiting the nystrom method for improved large-scale machine learning, J. Mach. Learn. Res., 28, 3, 567-575, (2013)
[42]	Sun, S.; Zhao, J.; Zhu, J., A review of Nyström methods for large-scale machine learning, Inf. Fusion, 26, 35-48, (2015)
[43]	Hammond, D. K.; Vandergheynst, P.; Gribonval, R., Wavelets on graphs via spectral graph theory, Appl. Comput. Harmon. Anal., 30, 2, 129-150, (2011) · Zbl 1213.42091
[44]	Chapelle, O.; Schlkopf, B.; Zien, A., Semi-supervised learning, (2010), The MIT Press
[45]	Zhu, X.; Ghahramani, Z.; Lafferty, J. D., Semi-supervised learning using Gaussian fields and harmonic functions, (Machine Learning, Proceedings of the Twentieth International Conference, ICML, August 21-24, 2003, Washington, DC, USA, (2003)), 912-919
[46]	Zhou, D.; Bousquet, O.; Lal, T. N.; Weston, J.; Schölkopf, B., Learning with local and global consistency, (Thrun, S.; Saul, L. K.; Schölkopf, B., Advances in Neural Information Processing Systems, vol. 16, (2004), MIT Press), 321-328
[47]	Belkin, M.; Niyogi, P.; Sindhwani, V., Manifold regularization: a geometric framework for learning from labeled and unlabeled examples, J. Mach. Learn. Res., 7, 2399-2434, (2006) · Zbl 1222.68144
[48]	Bengio, Y.; Delalleau, O.; Roux, N. L., Label propagation and quadratic criterion, 193-216, (2006), MIT Press
[49]	Wang, Y.-X.; Sharpnack, J.; Smola, A.; Tibshirani, R. J., Trend filtering on graphs, (International Conference on Artificial Intelligence and Statistics, (2015)), 1042-1050
[50]	Belkin, M.; Niyogi, P., Using manifold structure for partially labelled classification, (Becker, S.; Thrun, S.; Obermayer, K., Advances in Neural Information Processing Systems, vol. 15, (2003), MIT Press), 953-960
[51]	Fergus, R.; Weiss, Y.; Torralba, A., Semi-supervised learning in gigantic image collections, (Bengio, Y.; Schuurmans, D.; Lafferty, J. D.; Williams, C. K.I.; Culotta, A., Advances in Neural Information Processing Systems, vol. 22, (2009), Curran Associates, Inc.), 522-530
[52]	Settles, B., Active learning, vol. 6, (2012), Morgan & Claypool Publishers
[53]	Fu, Y.; Zhu, X.; Li, B., A survey on instance selection for active learning, Knowl. Inf. Syst., 35, 2, 249-283, (2012)
[54]	Gu, Q.; Han, J., Towards active learning on graphs: an error bound minimization approach, (2012 IEEE 12th International Conference on Data Mining, (2012)), 882-887
[55]	M. Bilgic, L. Getoor, Active inference for collective classification, in: AAAI Conference on Artificial Intelligence, 2010.
[56]	Ji, M.; Han, J., A variance minimization criterion to active learning on graphs, (International Conference on Artificial Intelligence and Statistics, (2012)), 556-564
[57]	Ma, Y.; Garnett, R.; Schneider, J., σ-optimality for active learning on Gaussian random fields, (Burges, C. J.C.; Bottou, L.; Welling, M.; Ghahramani, Z.; Weinberger, K. Q., Advances in Neural Information Processing Systems, vol. 26, (2013), Curran Associates, Inc.), 2751-2759
[58]	Zhang, C.; Florêncio, D.; Chou, P. A., Graph signal processing - a probabilistic framework, (April 2015), Tech. rep., Microsoft Research
[59]	Gadde, A.; Ortega, A., A probabilistic interpretation of sampling theory of graph signals, (2015 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP, (2015)), 3257-3261
[60]	Napoli, E. D.; Polizzo, E.; Saad, Y., Efficient estimation of eigenvalue counts in an interval
[61]	Perraudin, N.; Paratte, J.; Shuman, D.; Kalofolias, V.; Vandergheynst, P.; Hammond, D. K., Gspbox: a toolbox for signal processing on graphs
[62]	Shahid, N.; Perraudin, N.; Kalofolias, V.; Vandergheynst, P., Fast robust PCA on graphs
[63]	Tremblay, N.; Puy, G.; Gribonval, R.; Vandergheynst, P., Compressive spectral clustering, (Machine Learning, Proceedings of the Thirty-Third International Conference, ICML 2016, June 20-22, New York City, USA, (2016))
[64]	Tropp, J. A., User-friendly tail bounds for sums of random matrices, Found. Comput. Math., 12, 4, 389-434, (2012) · Zbl 1259.60008
[65]	Tropp, J. A., Improved analysis of the subsampled randomized Hadamard transform, Adv. Adapt. Data Anal., 3, 01n02, 115-126, (2011) · Zbl 1232.15029
[66]	Baraniuk, R. G.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 3, 253-263, (2008) · Zbl 1177.15015
[67]	Vershynin, R., Introduction to the non-asymptotic analysis of random matrices, (Compressed Sensing, Theory and Applications, (2012), Cambridge University Press), 210-268