Compressive Recovery of Signals Defined On Perturbed Graphs

Recovery of graph signals from compressively sensed (CS) measurements is an important problem in image reconstruction, sensor networks and group testing. In some cases, the the observed graph may contain a few edge perturbations relative to the ground truth graph. This impedes recovery of signals which are sparse in the Graph Fourier Transform (GFT) basis of the ground truth graph. We present cross-validation based algorithms, along with recovery guarantees, for the novel ‘Compressive Perturbed Graph Recovery’ problem, where the signal is recovered from compressive measurements while correcting the graph perturbations. We present an application to compressive image reconstruction, where undesirable graph edges linking pixels with significant intensity difference constitute the graph perturbations. We also validate our algorithms on signals which have a sparse representation in the GFT basis of commonly-used graph models. Our algorithms outperform baselines which ignore the perturbations or use first order approximations to the GFT basis perturbations.