# Sparse Recovery over Graph Incidence Matrices

arXiv: https://arxiv.org/abs/1803.09631 · HTML: https://mlsanity.com/paper/1803.09631/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Mar 2018.

## Built on by (most cited first, 1 of 1)

- [Recovering lost and absent information in temporal networks](https://mlsanity.com/paper/2107.10835/) (2021)

## Abstract (arXiv)

Classical results in sparse recovery guarantee the exact reconstruction of s-sparse signals under assumptions on the dictionary that are either too strong or NP-hard to check. Moreover, such results may be pessimistic in practice since they are based on a worst-case analysis. In this paper, we consider the sparse recovery of signals defined over a graph, for which the dictionary takes the form of an incidence matrix. We derive necessary and sufficient conditions for sparse recovery, which depend on properties of the cycles of the graph that can be checked in polynomial time. We also derive support-dependent conditions for sparse recovery that depend only on the intersection of the cycles of the graph with the support of the signal. Finally, we exploit sparsity properties on the measurements and the structure of incidence matrices to propose a specialized sub-graph-based recovery algorithm that outperforms the standard ℓ1-minimization approach.