Sparse Recovery with Graph Constraints: Fundamental Limits and Measurement Construction
This paper addresses the problem of sparse recovery with graph constraints in the sense that the authors can take additive measurements over nodes only if they induce a connected sub-graph. They provide explicit measurement constructions for several special graphs. A general measurement construction algorithm is also proposed and evaluated. Network monitoring is an important module in the operation and management of communication networks, where network performance characteristics, such as traffic transmission rates and router queuing delays, should be monitored.