2010/08/05 by Weiyu Xu, Enrique Mallada, Xu, Weiyu +3
Computer Science · Engineering · Mathematics · #60C05 #68R10 #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Networking and Internet Architecture (cs.NI) #Sparse and Compressive Sensing Techniques #cs.IT #cs.NI #math.IT #msc:60C05 #msc:68R10
paper · pdf · doi:10.48550/arxiv.1008.0919
arxiv created 2010/08/05 · openalex publication_date 2010/08/05 · arxiv updated 2010/08/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ℓ1 minimization can provide theoretical guarantees for inferring such k-sparse vectors with O(k log(n)) path measurements from the graph.