Delaram Motamedvaziri (PhD ’13)
Prof. Venkatesh Saligrama, Prof. David Castañón
Funding: Department of Homeland Security, National Science Foundation
Background: Consider the problem of a decentralized network of J sensors, in which each sensor observes either all or some components of an underlying sparse signal ensemble. Sensors operate with no collaboration with each other or the fusion center. Each sensor transmits a subset of its linear measurements to the fusion center. The fusion center gathers the data sent by all sensors and reconstructs the signal. The goal is to compress data at each node efficiently for accurate reconstruction at the fusion center. Acording to conventional Compressive Sensing, reconstructing a k -sparse signal of length N is possible from only O(k log(N/k)) measurements. If we have a sensor network with J sensors observing a signal ensemble of length N, distributed Compresive Sensing suggests that we can use the underlying structure of the signal ensemble. Hence, at node i only O(k_i log(N_i/k_i)) measurements are needed where k_i and N_i are the local sparsity and the length of the signal observed by i-th sensor. This implies that:
- the signal observed by each sensor must be sparse, and
- this local sparsity must be known at each sensor node.
Description: We proved that for accurate reconstruction, there is no need to have local sparsity k_i. As long as the signal ensemble is k-sparse, we can reconstruct the signal with a Bernoulli scheme with probability p. Although the original signal is sparse, there is no guarantee on local sparsity at each node. To manage decentralized reconstruction, we propose a new Bernoulli Sampling scheme. This scheme associates an independent Bernoulli trial, with parameter p, to each measurement that a sensor makes. The sensor makes a measurement, if the outcome of the associated Bernoulli trial is 1. The measurement is ignored otherwise. We show that it is possible to accurately reconstruct the signal through Bernoulli sampled measurements, with no assumption on the local sparsity, if the success probability of the Bernoulli sampling exceeds a lower bound. This lower bound is solely related to the global sparsity of the signal ensemble. We also show the recovery through Bernoulli sampling is robust to noisy measurements and packet loss.
Results: Each sensor makes and transmits a measurement with probability p and ignores the measurement with probability 1-p. We showed that if p=O(k/n*log(N/k)), where k is the global sparsity of the ensemble, the reconstruction is possible.
D. Motamedvaziri, V. Saligrama, D. Castanon, “Decentralized Compressive Sening”, Alllerton Conference, 2010.