Sparsity without the complexity: Loss localisation using tree measurements
- Publication Type:
- Conference Proceeding
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7289 LNCS (PART 1), pp. 289 - 303
- Issue Date:
- 2012-06-05
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| Pages from 10.1007_978-3-642-30045-5.pdf | Published version | 636.97 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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 ℓ 1 minimization recovers the true underlying solution. We present a fast single-pass linear algorithm for ℓ 1 minimization and prove that a minimum ℓ 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. © 2012 IFIP International Federation for Information Processing.
Please use this identifier to cite or link to this item: