Sparse Recovery with Graph Constraints: Fundamental Limits and Measurement Construction

2011/08/01 by Wang, Meng, Xu, Weiyu, Mallada, Enrique +1
#FOS: Computer and information sciences #Information Theory (cs.IT) #Networking and Internet Architecture (cs.NI)

paper · doi:10.48550/arxiv.1108.0443

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.

Related

• Sparse Recovery with Graph Constraints
• Compressive Sensing over Graphs
• Information Recovery from Pairwise Measurements
• Sparse Recovery of Positive Signals with Minimal Expansion
• Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics