Sparse graph signals – uncertainty principles and recovery

We study signals that are sparse either on the vertices of a graph or in the graph spectral domain. Recent results on the algebraic properties of random integer matrices as well as on the boundedness of eigenvectors of random matrices imply two types of support size uncertainty principles for graph signals. Indeed, the algebraic properties imply uniqueness results if a sparse signal is sampled at any set of minimal size in the other domain. The boundedness properties of eigenvectors imply stable reconstruction by basis pursuit if a sparse signal is sampled at a slightly larger randomly selected set in the other domain.