  In this work, we present a theoretical study of signals with sparse
representations in the vertex domain of a graph, which is primarily motivated
by the discrepancy arising from respectively adopting a synthesis and analysis
view of the graph Laplacian matrix. Sparsity on graphs and, in particular, the
characterization of the subspaces of signals which are sparse with respect to
the connectivity of the graph, as induced by analysis with a suitable graph
operator, remains in general an opaque concept which we aim to elucidate. By
leveraging the theory of cosparsity, we present a novel (co)sparse graph
Laplacian-based signal model and characterize the underlying (structured)
(co)sparsity, smoothness and localization of its solution subspaces on
undirected graphs, while providing more refined statements for special cases
such as circulant graphs. Ultimately, we substantiate fundamental discrepancies
between the cosparse analysis and sparse synthesis models in this structured
setting, by demonstrating that the former constitutes a special, constrained
instance of the latter.
