  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 $\ell_1$ minimization recovers the true underlying
solution. We present a fast single-pass linear algorithm for $\ell_1$
minimization and prove that a minimum $\ell_1$ 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.
