Compressive Sensing over Graphs

Details Compressive Sensing over Graphs Compressive Sensing over Graphs

2010-08-05

arxiv.org/abs/1008.0919v1

Computer Science

Information Theory

Scientific paper

In this paper, motivated by network inference and tomography applications, we study the problem of compressive sensing for sparse signal vectors over graphs. In particular, we are interested in recovering sparse vectors representing the properties of the edges from a graph. Unlike existing compressive sensing results, the collective additive measurements we are allowed to take must follow connected paths over the underlying graph. For a sufficiently connected graph with $n$ nodes, it is shown that, using $O(k \log(n))$ path measurements, we are able to recover any $k$-sparse link vector (with no more than $k$ nonzero elements), even though the measurements have to follow the graph path constraints. We further show that the computationally efficient $\ell_1$ minimization can provide theoretical guarantees for inferring such $k$-sparse vectors with $O(k \log(n))$ path measurements from the graph.

Affiliated with

Also associated with

No associations

Rating

Compressive Sensing over Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compressive Sensing over Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressive Sensing over Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-438219