Compressive sensing over graphs: How many measurements are needed?

Weiyu Xu; Ao Tang

doi:10.1109/ALLERTON.2010.5706964

Back

Conference proceeding

Compressive sensing over graphs: How many measurements are needed?

Weiyu Xu and Ao Tang

2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.615-619

09/2010

DOI: 10.1109/ALLERTON.2010.5706964

View Online

Abstract

In this paper, we study the problem of compressive sensing for sparse signal vectors generated over the graphs. The signal vectors to be recovered are sparse vectors representing the parameters of the links over the graphs. The collective additive measurements we are allowed to take must follow connected paths over the underlying graphs. For a sufficiently connected graph with n nodes, using O(k log(n)) path measurements, it is shown that we are able to recover any sparse link vector with no more than k nonzero elements, even though the measurements have to follow the graph path constraints.

Additives

Compressed sensing

Delay

Monitoring

Null space

Testing

Vectors

Details

Title: Subtitle: Compressive sensing over graphs: How many measurements are needed?
Creators: Weiyu Xu - Cornell University
Ao Tang - Cornell University
Resource Type: Conference proceeding
Publication Details: 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp.615-619
DOI: 10.1109/ALLERTON.2010.5706964
Publisher: IEEE
Language: English
Date published: 09/2010
Academic Unit: Electrical and Computer Engineering
Record Identifier: 9984197412202771

Metrics

18 Record Views