We study network loss tomography based on observing average loss rates over a set of paths forming a tree -- a severely underdetermined linear problem for the unknown link loss probabilities. We examine in detail the role of sparsity as a regularising principle, pointing out that the problem is technically distinct from others in the compressed sensing literature. While sparsity has been applied in the context of tomography, key questions regarding uniqueness and recovery remain unanswered. Our work exploits the tree structure of path measurements to derive sufficient conditions for sparse solutions to be unique and the condition that @math minimization recovers the true underlying solution. We present a fast single-pass linear algorithm for @math minimization and prove that a minimum @math solution is both unique and sparsest for tree topologies. By considering the placement of lossy links within trees, we show that sparse solutions remain unique more often than is commonly supposed. We prove similar results for a noisy version of the problem.
In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with @math nodes, it is shown that, using @math path measurements, we are able to recover any @math -sparse link vector (with no more than @math nonzero elements), even though the measurements have to follow the graph path constraints. We further show that the computationally efficient @math minimization can provide theoretical guarantees for inferring such @math -sparse vectors with @math path measurements from the graph.