{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:51:01Z","timestamp":1760233861627,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this paper, we focus on the bandlimited graph signal sampling problem. To sample graph signals, we need to find small-sized subset of nodes with the minimal optimal reconstruction error. We formulate this problem as a subset selection problem, and propose an efficient Pareto Optimization for Graph Signal Sampling (POGSS) algorithm. Since the evaluation of the objective function is very time-consuming, a novel acceleration algorithm is proposed in this paper as well, which accelerates the evaluation of any solution. Theoretical analysis shows that POGSS finds the desired solution in quadratic time while guaranteeing nearly the best known approximation bound. Empirical studies on both Erdos-Renyi graphs and Gaussian graphs demonstrate that our method outperforms the state-of-the-art greedy algorithms.<\/jats:p>","DOI":"10.3390\/s21041415","type":"journal-article","created":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T21:59:58Z","timestamp":1613685598000},"page":"1415","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Near-Optimal Graph Signal Sampling by Pareto Optimization"],"prefix":"10.3390","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3124-2793","authenticated-orcid":false,"given":"Dongqi","family":"Luo","sequence":"first","affiliation":[{"name":"Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3206-1388","authenticated-orcid":false,"given":"Binqiang","family":"Si","sequence":"additional","affiliation":[{"name":"School of Instrumentation Science and Opto-Electronics Engineering, Beijing Information Science and Technology University, Beijing 100192, China"}]},{"given":"Saite","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China"}]},{"given":"Fan","family":"Yu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China"}]},{"given":"Jihong","family":"Zhu","sequence":"additional","affiliation":[{"name":"Department of Precision Instrument, Tsinghua University, Beijing 100084, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1109\/JPROC.2018.2820126","article-title":"Graph signal processing: Overview, challenges, and applications","volume":"106","author":"Ortega","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"868","DOI":"10.1109\/JPROC.2018.2798928","article-title":"A graph signal processing perspective on functional brain imaging","volume":"106","author":"Huang","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MSP.2017.2693418","article-title":"Geometric deep learning: Going beyond Euclidean data","volume":"34","author":"Bronstein","year":"2017","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1049\/iet-ipr.2017.0965","article-title":"Efficient image steganography using graph signal processing","volume":"12","author":"Sharma","year":"2018","journal-title":"IET Image Process."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Pang, J., Cheung, G., Hu, W., and Au, O.C. (2014, January 9\u201312). Redefining self-similarity in natural images for denoising using graph signal gradient. Proceedings of the Signal and Information Processing Association Annual Summit and Conference (APSIPA), 2014 Asia-Pacific, Chiang Mai, Thailand.","DOI":"10.1109\/APSIPA.2014.7041627"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Turk, G., and Levoy, M. (1994, January 24\u201329). Zippered polygon meshes from range images. Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, Orlando, FL, USA.","DOI":"10.1145\/192161.192241"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1109\/TPAMI.2007.70735","article-title":"Riemannian manifold learning","volume":"30","author":"Lin","year":"2008","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Sakiyama, A., Tanaka, Y., Tanaka, T., and Ortega, A. (2016, January 20\u201325). Efficient sensor position selection using graph signal sampling theory. Proceedings of the 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Shanghai, China.","DOI":"10.1109\/ICASSP.2016.7472874"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1109\/TSP.2017.2771730","article-title":"Fast resampling of three-dimensional point clouds via graphs","volume":"66","author":"Chen","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1109\/TSP.2017.2755586","article-title":"Greedy sampling of graph signals","volume":"66","author":"Chamon","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Hashemi, A., Shafipour, R., Vikalo, H., and Mateos, G. (2018, January 15\u201320). Sampling and reconstruction of graph signals via weak submodularity and semidefinite relaxation. Proceedings of the 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Calgary, AB, Canada.","DOI":"10.1109\/ICASSP.2018.8461925"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1109\/LCSYS.2018.2845943","article-title":"Identification of sparse reciprocal graphical models","volume":"2","author":"Alpago","year":"2018","journal-title":"IEEE Control. Syst. Lett."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Ciccone, V., Ferrante, A., and Zorzi, M. (2018, January 17\u201319). Robust identification of \u201cSparse Plus Low-rank\u201d graphical models: An optimization approach. Proceedings of the 2018 IEEE Conference on Decision and Control (CDC), Miami, FL, USA.","DOI":"10.1109\/CDC.2018.8619796"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1137\/S0097539792240406","article-title":"Sparse approximate solutions to linear systems","volume":"24","author":"Natarajan","year":"1995","journal-title":"SIAM J. Comput."},{"key":"ref_15","unstructured":"Das, A., and Kempe, D. (July, January 28). Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. Proceedings of the 2011 IEEE International Conference on Machine Learning (ICML), Washington, DC, USA."},{"key":"ref_16","first-page":"1774","article-title":"Subset selection by Pareto Optimization","volume":"Volume 28","author":"Cortes","year":"2015","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref_17","first-page":"2408","article-title":"Subset selection by Pareto Optimization with recombination","volume":"34","author":"Qian","year":"2020","journal-title":"Proc. AAAI Conf. Artif. Intell."},{"key":"ref_18","first-page":"3560","article-title":"Subset selection under noise","volume":"Volume 30","author":"Guyon","year":"2017","journal-title":"Advances in Neural Information Processing Systems"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"6510","DOI":"10.1109\/TSP.2015.2469645","article-title":"Discrete signal processing on graphs: Sampling theory","volume":"63","author":"Chen","year":"2015","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1050","DOI":"10.1109\/PROC.1986.13587","article-title":"Generalization of the matrix inversion lemma","volume":"74","author":"Tylavsky","year":"1986","journal-title":"Proc. IEEE"},{"key":"ref_21","first-page":"890","article-title":"Robust maximization of non-submodular objectives","volume":"Volume 84","author":"Storkey","year":"2018","journal-title":"Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Zhou, Z.H., Yu, Y., and Qian, C. (2019). Evolutionary learning: Advances in Theories and Algorithms, Springer. [1st ed.].","DOI":"10.1007\/978-981-13-5956-9"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1109\/TSP.2008.2007095","article-title":"Sensor selection via Convex Optimization","volume":"57","author":"Joshi","year":"2009","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3328","DOI":"10.1016\/j.patcog.2008.05.007","article-title":"Graph spectral image smoothing using the heat kernel","volume":"41","author":"Zhang","year":"2008","journal-title":"Pattern Recognit."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1415\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:25:35Z","timestamp":1760160335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/4\/1415"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":24,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["s21041415"],"URL":"https:\/\/doi.org\/10.3390\/s21041415","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2021,2,18]]}}}