Motivated by network tomography problems, in this talk, we discuss the problem
of sparse recovery with graph constraints in the sense that we can take
additive
measurements over nodes only if they induce a connected subgraph. We provide
explicit measurement constructions for several special graphs including line,
2-D grid and tree. A general measurement construction algorithm is also
proposed
and evaluated. For any given graph G with n nodes, we derive order optimal
upper
bounds of the minimum
number of measurements needed to recover any k-sparse vector over G. Our study
suggests that this number may serve as a graph connectivity metric.