Sparse Recovery With Graph Constraints

DOI10.1109/TIT.2014.2376955MaRDI QIDQ2978787zbMATH OpenOpenAlexFDO

Authors Meng Wang, Weiyu Xu, Enrique Mallada, Ao Tang

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.2829

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: Sparse recovery can recover sparse signals from a set of underdetermined linear measurements. Motivated by the need to monitor 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 ErdH{o}s-R'enyi random graph as an example, we characterize the dependence of $M_{k,n}^G$ on the graph structure.

Recommendations

• Recovering sparse graphs
• Sparse recovery with integrality constraints
• Sparse Recovery
• Theoretical guarantees for graph sparse coding
• Graph optimization for dimensionality reduction with sparsity constraints
• Sparse recovery from saturated measurements
• Methods for sparse and low-rank recovery under simplex constraints
• Sparse Approximation and Recovery by Greedy Algorithms
• Sparse recovery algorithms: sufficient conditions in terms of restricted isometry constants
• Lower bounds for sparse recovery

Cited in

(1)

• Signal Recovery on Graphs: Variation Minimization

This page was built for publication: Sparse Recovery With Graph Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978787)