Sparse Recovery With Graph Constraints
- Creators
- Wang, Meng
- Xu, Weiyu
- Mallada, Enrique
- Tang, Ao
Abstract
Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor the key characteristics of large-scale networks from a limited number of measurements, this paper addresses the problem of recovering sparse signals in the presence of network topological constraints. Unlike conventional sparse recovery where a measurement can contain any subset of the unknown variables, we use a graph to characterize the topological constraints and allow an additive measurement over nodes (unknown variables) only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs, and the number of measurements by our construction is less than that needed by existing random constructions. Moreover, our construction for a line network is provably optimal in the sense that it requires the minimum number of measurements. A measurement construction algorithm for general graphs is also proposed and evaluated. For any given graph G with n nodes, we derive bounds of the minimum number of measurements needed to recover any k-sparse vector over G (M_(k,n)^G). Using the Erdõs-Rényi random graph as an example, we characterize the dependence of M_(k,n)^G on the graph structure. This paper suggests that M_(k,n)^G may serve as a graph connectivity metric.
Additional Information
© 2014 IEEE. Manuscript received September 14, 2013; Revised August 3, 2014; Accepted November 9, 2014. Date of publication December 4, 2014; Date of current version January 16, 2015. This work was supported in part by the Division of Computing and Communication Foundations under Grant CCF-0835706, in part by the Air Force Office of Scientific Research, Arlington, VA, USA, under Grant 9550-12-1-0362, and in part by the Office of Naval Research, Arlington, under Grant N00014-11-1-0131. This paper was presented at the 2012 IEEE INFOCOM [41].Attached Files
Submitted - 1207.2829v2.pdf
Files
Name | Size | Download all |
---|---|---|
md5:82390731eeb017cd3f548fc9653eb3c9
|
531.6 kB | Preview Download |
Additional details
- Eprint ID
- 55268
- Resolver ID
- CaltechAUTHORS:20150226-140505734
- CCF-0835706
- NSF
- 9550-12-1-0362
- Air Force Office of Scientific Research (AFOSR)
- N00014-11-1-0131
- Office of Naval Research (ONR)
- Created
-
2015-02-26Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field