Published in

2012 Proceedings IEEE INFOCOM

DOI: 10.1109/infcom.2012.6195562

Links

Tools

Export citation

Search in Google Scholar

Sparse Recovery with Graph Constraints: Fundamental Limits and Measurement Construction

Journal article published in 2011 by Meng Wang, Meng Wang, Weiyu Xu, Enrique Mallada, Ao Tang
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Red circle
Published version: archiving forbidden
Policy details
Data provided by SHERPA/RoMEO

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^G_{k,n}$). Our study suggests that $M^G_{k,n}$ may serve as a graph connectivity metric.