Conference proceeding
Compressive sensing over graphs
2011 Proceedings IEEE INFOCOM, pp.2087-2095
04/2011
DOI: 10.1109/INFCOM.2011.5935018
Abstract
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 n nodes, it is shown that, using O(k log(n)) path measurements, we are able to recover any k-sparse link vector (with no more than k nonzero elements), even though the measurements have to follow the graph path constraints. We mainly show that the computationally efficient ℓ 1 minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.
Details
- Title: Subtitle
- Compressive sensing over graphs
- Creators
- Weiyu Xu - Cornell UniversityEnrique Mallada - Cornell UniversityAo Tang - Cornell University
- Resource Type
- Conference proceeding
- Publication Details
- 2011 Proceedings IEEE INFOCOM, pp.2087-2095
- DOI
- 10.1109/INFCOM.2011.5935018
- ISSN
- 0743-166X
- eISSN
- 2641-9874
- Publisher
- IEEE
- Language
- English
- Date published
- 04/2011
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197560302771
Metrics
13 Record Views