Sparsity without the Complexity: Loss Localisation Using Tree Measurements

Abstract : 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.
Type de document :
Communication dans un congrès
Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7289 (Part I), pp.289-303, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30045-5_22〉
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01531123
Contributeur : Hal Ifip <>
Soumis le : jeudi 1 juin 2017 - 11:34:57
Dernière modification le : jeudi 1 juin 2017 - 15:00:58
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 18:41:27

Fichier

978-3-642-30045-5_22_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Vijay Arya, Darryl Veitch. Sparsity without the Complexity: Loss Localisation Using Tree Measurements. Robert Bestak; Lukas Kencl; Li Erran Li; Joerg Widmer; Hao Yin. 11th International Networking Conference (NETWORKING), May 2012, Prague, Czech Republic. Springer, Lecture Notes in Computer Science, LNCS-7289 (Part I), pp.289-303, 2012, NETWORKING 2012. 〈10.1007/978-3-642-30045-5_22〉. 〈hal-01531123〉

Partager

Métriques

Consultations de la notice

53

Téléchargements de fichiers

26