Conference proceeding
Sparse recovery with graph constraints: Fundamental limits and measurement construction
2012 Proceedings IEEE INFOCOM, pp.1871-1879
03/2012
DOI: 10.1109/INFCOM.2012.6195562
Abstract
This paper addresses the problem of sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G (M k,n G ). Our study suggests that M k,n G may serve as a graph connectivity metric.
Details
- Title: Subtitle
- Sparse recovery with graph constraints: Fundamental limits and measurement construction
- Creators
- Meng Wang - Cornell UniversityWeiyu Xu - Cornell UniversityEnrique Mallada - Cornell UniversityAo Tang - Cornell University
- Resource Type
- Conference proceeding
- Publication Details
- 2012 Proceedings IEEE INFOCOM, pp.1871-1879
- DOI
- 10.1109/INFCOM.2012.6195562
- ISSN
- 0743-166X
- eISSN
- 2641-9874
- Publisher
- IEEE
- Language
- English
- Date published
- 03/2012
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197114302771
Metrics
15 Record Views