Recovery of Graph Signals From Sign Measurements

Sampling and interpolation of continuous graph signals have been extensively studied, in order to reconstruct or estimate the entire graph signal from the signal values on a subset of vertices. Whereas in a lot of real-world scenarios, only the signs of signals are available. For example, a rating system may only provide simple options such as "like" or "dislike". We are interested in whether it is possible to recover the original signal from such coarse information. In this paper, the reconstruction of bandlimited graph signals based on sign measurements is discussed and a greedy sampling strategy is proposed. The simulation experiments are presented, and the greedy sampling algorithm is compared with the random sampling algorithm, which verifies the feasibility of the proposed approach.