Graph Signal Sampling via Reinforcement Learning

Modern information processing systems generate massive datasets which are often strongly heterogeneous, e.g., partially labeled mixtures of different media (audio, video, text). A quite successful approach to such datasets is based on representing the data as networks or graphs. In particular, we represent datasets by graph signals defined over an underlying graph, which reflects similarities between individual data points. The graph signal values encode label information which often conforms to a clustering hypothesis, i.e., the signal values (labels) of close-by nodes (similar data points) are similar. Two core problems considered within graph signal processing (GSP) are (i) how to sample them, i.e., which signal values provide the most information about the entire dataset, and (ii) how to recover the entire graph signal from these few signal values (samples). These problems have been studied in [1]-[6] which discussed convex optimization methods for recovering a graph signal from a small number of signal values observed on the nodes belonging to a given (small) sampling set. Sufficient conditions on the sampling set and clustering structure such that these convex methods are successful have been discussed in [4], [7].