M. Newman, Networks: an introduction, 2010.
DOI : 10.1093/acprof:oso/9780199206650.001.0001

D. Shuman, S. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains, IEEE Signal Processing Magazine, vol.30, issue.3, pp.83-98, 2013.
DOI : 10.1109/MSP.2012.2235192

A. Sandryhaila and J. Moura, Big Data Analysis with Signal Processing on Graphs: Representation and processing of massive data sets with irregular structure, IEEE Signal Processing Magazine, vol.31, issue.5, pp.80-90, 2014.
DOI : 10.1109/MSP.2014.2329213

M. Unser, Sampling-50 years after Shannon, Proceedings of the IEEE, vol.88, issue.4, pp.569-587, 2000.
DOI : 10.1109/5.843002

C. Shannon, Communication in the Presence of Noise, Proceedings of the IRE, vol.37, issue.1, pp.10-21, 1949.
DOI : 10.1109/JRPROC.1949.232969

J. D. Mcewen and Y. Wiaux, A Novel Sampling Theorem on the Sphere, IEEE Transactions on Signal Processing, vol.59, issue.12, 2011.
DOI : 10.1109/TSP.2011.2166394

K. Gröchenig, Reconstruction Algorithms in Irregular Sampling, Mathematics of Computation, vol.59, issue.199, pp.181-194, 1992.
DOI : 10.2307/2152989

J. J. Benedetto, Irregular Sampling and Frames, Tutorial in Theory and Applications, pp.445-507, 1992.
DOI : 10.1016/B978-0-12-174590-5.50020-4

E. J. Candès, Compressive sampling, Proceedings of the international congress of mathematicians, pp.1433-1452, 2006.
DOI : 10.4171/022-3/69

S. Chen, R. Varma, A. Sandryhaila, and J. Kovacevic, Discrete Signal Processing on Graphs: Sampling Theory, IEEE Transactions on Signal Processing, vol.63, issue.24, pp.1-1, 2015.
DOI : 10.1109/TSP.2015.2469645

A. Anis, A. Gadde, and A. Ortega, Towards a sampling theorem for signals on arbitrary graphs, 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.3864-3868, 2014.
DOI : 10.1109/ICASSP.2014.6854325

S. Narang and A. Ortega, Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs, IEEE Transactions on Signal Processing, vol.61, issue.19, pp.4673-4685, 2013.
DOI : 10.1109/TSP.2013.2273197

I. Pesenson, Sampling in Paley-Wiener spaces on combinatorial graphs, Transactions of the American Mathematical Society, vol.360, issue.10, pp.5603-5627, 2008.
DOI : 10.1090/S0002-9947-08-04511-X

I. Z. Pesenson and M. Z. Pesenson, Sampling, Filtering and Sparse Approximations on??Combinatorial Graphs, Journal of Fourier Analysis and Applications, vol.38, issue.1, pp.921-942, 2010.
DOI : 10.1007/s00041-009-9116-7

A. Anis, A. E. Gamal, S. Avestimehr, and A. Ortega, Asymptotic justification of bandlimited interpolation of graph signals for semi-supervised learning, 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.5461-5465, 2015.
DOI : 10.1109/ICASSP.2015.7179015

S. Chen, A. Sandryhaila, and J. Kovacevic, Sampling theory for graph signals, 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.3392-3396, 2015.
DOI : 10.1109/ICASSP.2015.7178600

A. Anis, A. Gadde, and A. Ortega, Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies, IEEE Transactions on Signal Processing, vol.64, issue.14, pp.1-1, 2016.
DOI : 10.1109/TSP.2016.2546233

H. Nguyen and M. Do, Downsampling of Signals on Graphs Via Maximum Spanning Trees, IEEE Transactions on Signal Processing, vol.63, issue.1, pp.182-191, 2015.
DOI : 10.1109/TSP.2014.2369013

D. I. Shuman, M. J. Faraji, and P. Vandergheynst, A Multiscale Pyramid Transform for Graph Signals, IEEE Transactions on Signal Processing, vol.64, issue.8, pp.2119-2134, 2016.
DOI : 10.1109/TSP.2015.2512529

J. Irion and S. Naoki, Applied and computational harmonic analysis on graphs and networks, Proc. SPIE Conf. WAVELET XVI, 2015.

N. Tremblay and P. Borgnat, Subgraph-Based Filterbanks for Graph Signals, IEEE Transactions on Signal Processing, vol.64, issue.15, pp.1-1, 2016.
DOI : 10.1109/TSP.2016.2544747

URL : https://hal.archives-ouvertes.fr/hal-01243889

A. Agaskar and Y. Lu, A spectral graph uncertainty principle Information Theory, IEEE Transactions on, vol.59, issue.7, pp.4338-4356, 2013.

M. Rabbat and V. Gripon, Towards a spectral characterization of signals supported on small-world networks, 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.4793-4797, 2014.
DOI : 10.1109/ICASSP.2014.6854512

URL : https://hal.archives-ouvertes.fr/hal-01057352

Y. Nakatsukasa, N. Saito, and E. Woei, Mysteries around the graph Laplacian eigenvalue 4, Linear Algebra and its Applications, vol.438, issue.8, pp.3231-3246, 2013.
DOI : 10.1016/j.laa.2012.12.012

G. Puy, P. Vandergheynst, and Y. Wiaux, On Variable Density Compressive Sampling, IEEE Signal Processing Letters, vol.18, issue.10, pp.595-598, 2011.
DOI : 10.1109/LSP.2011.2163712

F. Krahmer and R. Ward, Stable and Robust Sampling Strategies for Compressive Imaging, IEEE Transactions on Image Processing, vol.23, issue.2, pp.612-622, 2013.
DOI : 10.1109/TIP.2013.2288004

B. Adcock, A. C. Hansen, C. Poon, and B. Roman, BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING, Forum of Mathematics, Sigma, vol.94840, 2013.
DOI : 10.1017/S0962492900002816

S. Chen, R. Varma, A. Singh, and J. Kovacevi, Signal recovery on graphs: Random versus experimentally designed sampling, 2015 International Conference on Sampling Theory and Applications (SampTA), pp.337-341, 2015.
DOI : 10.1109/SAMPTA.2015.7148908

F. Chung, Spectral graph theory, 1997.
DOI : 10.1090/cbms/092

E. Candes and J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Problems, vol.23, issue.3, pp.969-985, 2007.
DOI : 10.1088/0266-5611/23/3/008

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, ser. Applied and Numerical Harmonic Analysis, 2013.

M. Lustig, D. Donoho, and J. M. Pauly, Sparse MRI: The application of compressed sensing for rapid MR imaging, Magnetic Resonance in Medicine, vol.170, issue.6, pp.1182-1195, 2007.
DOI : 10.1002/mrm.21391

N. Chauffert, P. Ciuciu, and P. Weiss, Variable density compressed sensing in MRI. Theoretical vs heuristic sampling strategies, 2013 IEEE 10th International Symposium on Biomedical Imaging, pp.298-301, 2013.
DOI : 10.1109/ISBI.2013.6556471

URL : https://hal.archives-ouvertes.fr/hal-00848271

C. Boyer, J. Bigot, and P. Weiss, Compressed sensing with structured sparsity and structured acquisition, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01149456

J. Bigot, C. Boyer, and P. Weiss, An Analysis of Block Sampling Strategies in Compressed Sensing, IEEE Transactions on Information Theory, vol.62, issue.4, pp.2125-2139, 2016.
DOI : 10.1109/TIT.2016.2524628

URL : https://hal.archives-ouvertes.fr/hal-00823711

P. Drineas, M. M. Ismail, M. W. Mahoney, and D. P. Woodruff, Fast approximation of matrix coherence and statistical leverage, J. Mach. Learn. Res, vol.13, p.34753506, 2012.

P. Drineas, M. W. Mahoney, and S. Muthukrishnan, regression and applications, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm , SODA '06, pp.1127-1136, 2006.
DOI : 10.1145/1109557.1109682

M. W. Mahoney, Randomized Algorithms for Matrices and Data, Machine Learning, pp.123-224, 2011.
DOI : 10.1201/b11822-37

S. Chen, R. Varma, A. Singh, and J. Kovacevic, A statistical perspective of sampling scores for linear regression, 2016 IEEE International Symposium on Information Theory (ISIT), 2016.
DOI : 10.1109/ISIT.2016.7541560

P. Drineas, M. W. Mahoney, and S. Muthukrishnan, Relative-Error $CUR$ Matrix Decompositions, SIAM Journal on Matrix Analysis and Applications, vol.30, issue.2, pp.844-881, 2008.
DOI : 10.1137/07070471X

A. Gittens and M. Mahoney, Revisiting the nystrom method for improved large-scale machine learning, J. Mach. Learn. Res, vol.28, issue.3, pp.567-575, 2013.

S. Sun, J. Zhao, and J. Zhu, A review of nystrm methods for large-scale machine learning, Information Fusion, vol.26, pp.35-48, 2015.

D. K. Hammond, P. Vandergheynst, and R. Gribonval, Wavelets on graphs via spectral graph theory, Applied and Computational Harmonic Analysis, vol.30, issue.2, pp.129-150, 2011.
DOI : 10.1016/j.acha.2010.04.005

URL : https://hal.archives-ouvertes.fr/inria-00541855

X. Zhu, Z. Ghahramani, and J. D. Lafferty, Semi-supervised learning using gaussian fields and harmonic functions, Machine Learning, Proceedings of the Twentieth International Conference (ICML 2003), pp.912-919, 2003.

D. Zhou, O. Bousquet, T. N. Lal, J. Weston, and B. Schölkopf, Learning with local and global consistency, Advances in Neural Information Processing Systems 16, pp.321-328, 2004.

M. Belkin, P. Niyogi, and V. Sindhwani, Manifold regularization: A geometric framework for learning from labeled and unlabeled examples, J. Mach. Learn. Res, vol.7, pp.2399-2434, 2006.

Y. Bengio, O. Delalleau, and N. L. Roux, Label Propagation and Quadratic Criterion, p.193216, 2006.

Y. Wang, J. Sharpnack, A. Smola, and R. J. Tibshirani, Trend filtering on graphs, International Conference on Artificial Intelligence and Statistics, pp.1042-1050, 2015.

M. Belkin and P. Niyogi, Using manifold stucture for partially labeled classification, Advances in Neural Information Processing Systems 15, pp.953-960, 2003.

R. Fergus, Y. Weiss, and A. Torralba, Semi-supervised learning in gigantic image collections, Advances in Neural Information Processing Systems, pp.522-530, 2009.

B. Settles, Active Learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, vol.6, issue.1, 2012.
DOI : 10.2200/S00429ED1V01Y201207AIM018

Y. Fu, X. Zhu, and B. Li, A survey on instance selection for active learning, Knowledge and Information Systems, vol.28, issue.3, pp.249-283, 2012.
DOI : 10.1007/s10115-012-0507-8

Q. Gu and J. Han, Towards Active Learning on Graphs: An Error Bound Minimization Approach, 2012 IEEE 12th International Conference on Data Mining, pp.882-887, 2012.
DOI : 10.1109/ICDM.2012.72

M. Bilgic and L. Getoor, Active inference for collective classification, AAAI Conference on Artificial Intelligence, 2010.

M. Ji and J. Han, A variance minimization criterion to active learning on graphs, International Conference on Artificial Intelligence and Statistics, pp.556-564, 2012.

Y. Ma, R. Garnett, and J. Schneider, ? -optimality for active learning on gaussian random fields, Advances in Neural Information Processing Systems, pp.2751-2759, 2013.

C. Zhang, D. Florêncio, and P. A. Chou, Graph signal processing?a probabilistic framework, Microsoft Research, Tech. Rep, 2015.

A. Gadde and A. Ortega, A probabilistic interpretation of sampling theory of graph signals, 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp.3257-3261, 2015.
DOI : 10.1109/ICASSP.2015.7178573

E. D. Napoli, E. Polizzo, and Y. Saad, Efficient estimation of eigenvalue counts in an interval, Numerical Linear Algebra with Applications, vol.86, issue.2, 2013.
DOI : 10.1103/PhysRevE.69.057701

N. Perraudin, J. Paratte, D. Shuman, V. Kalofolias, P. Vandergheynst et al., Gspbox: A toolbox for signal processing on graphs, 2014.

N. Shahid, N. Perraudin, V. Kalofolias, and P. Vandergheynst, Fast Robust PCA on Graphs, IEEE Journal of Selected Topics in Signal Processing, vol.10, issue.4
DOI : 10.1109/JSTSP.2016.2555239

URL : https://hal.archives-ouvertes.fr/hal-01277624

N. Tremblay, G. Puy, R. Gribonval, and P. Vandergheynst, Compressive spectral clustering, Machine Learning, Proceedings of the Thirty-third International Conference, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01320214

J. A. Tropp, User-Friendly Tail Bounds for Sums of Random Matrices, Foundations of Computational Mathematics, vol.16, issue.2, pp.389-434, 2012.
DOI : 10.1007/s10208-011-9099-z

R. G. Baraniuk, M. Davenport, R. Devore, and M. Wakin, A Simple Proof of the Restricted Isometry Property for Random Matrices, Constructive Approximation, vol.159, issue.2, pp.253-263, 2008.
DOI : 10.1007/s00365-007-9003-x