# Eigendecomposition-Free Sampling Set Selection for Graph Signals

arXiv: https://arxiv.org/abs/1809.01827 · HTML: https://mlsanity.com/paper/1809.01827/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2018.

## Built on by (most cited first, 9 of 9)

- [Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment](https://mlsanity.com/paper/2208.08726/) (2022)
- [GraphReg: Dynamical Point Cloud Registration with Geometry-aware Graph Signal Processing](https://mlsanity.com/paper/2302.01109/) (2023)
- [Towards joint graph learning and sampling set selection from data](https://mlsanity.com/paper/2412.09753/) (2024)
- [Time-Vertex Machine Learning for Optimal Sensor Placement in Temporal Graph Signals: Applications in Structural Health Monitoring](https://mlsanity.com/paper/2512.19309/) (2025)
- [Graph Unfolding and Sampling for Transitory Video Keyframe Selection via Gershgorin Disc Alignment](https://mlsanity.com/paper/2408.01859/) (2024)
- [Reconstruction of Graph Signals on Complex Manifolds with Kernel Methods](https://mlsanity.com/paper/2505.15202/) (2025)
- [Point Cloud Quality Assessment Using the Perceptual Clustering Weighted Graph (PCW-Graph) and Attention Fusion Network](https://mlsanity.com/paper/2506.04081/) (2025)
- [Multilevel Graph Wavelet Compressed Sensing with Scale-Aware Neural Recovery](https://mlsanity.com/paper/2607.20857/) (2026)
- [Scalable Graph Coreset Selection via Greedy Sampling](https://mlsanity.com/paper/2607.27602/) (2026)

## Abstract (arXiv)

This paper addresses the problem of selecting an optimal sampling set for signals on graphs. The proposed sampling set selection (SSS) is based on a localization operator that can consider both vertex domain and spectral domain localization. We clarify the relationships among the proposed method, sensor position selection methods in machine learning, and conventional SSS methods based on graph frequency. In contrast to the conventional graph signal processing-based approaches, the proposed method does not need to compute the eigendecomposition of a variation operator, while still considering (graph) frequency information. We evaluate the performance of our approach through comparisons of prediction errors and execution time.