Group:Network Science Group
Title: Formulating Binary Compressive Sensing Decoding with Asymmetrical Property
Speaker: Nathan Hobbs, Liwen Xu University
Time: 2011-11-11 12:30-2011-11-11 14:00
Venue: FIT 1-222



I will be covering one aspect of the paper "Complexity of Data Collection, Aggregation, and Selection for Wireless Sensor Networks" by Xiang-Yang Li, Yajun Wang and Yu Wang. Specifically, the part regarding the Complexity of Data Selection for Wireless Sensor Networks regarding the randomized algorithm.


(modified) Abstract: Processing the gathered information efficiently is a key functionality for wireless sensor networks. In this article, we study the time complexity of data selection for a multi-hop network of n nodes. We first present a lower-bound on the complexity for the optimal methods, and then provide an asymptotically matching upper-bound on the complexity by presenting efficient distributed algorithms to solve these problems. For data selection, we show that any deterministic distributed algorithm needs Omega(Delta + DlogDN) time to find the median of all data items, where Delta is the maximum degree of the network and D is the diameter of the graph, and N is the total number of elements collected by sensors. We present a randomized algorithm that achieves this lower-bound with high probability.



Title: Formulating Binary Compressive Sensing Decoding with Asymmetrical Property

This paper mathematically analyzes the verification based message passing decoder for the binary compressive sensing (CS) compression problem, toward the goal of judging whether the decoding will be successful prior to the decoding process and of providing design guidelines of sensing matrices for better coding performance. For a biased binary source with unequal percentage of bit “0” and “1”, we observe that the recovery probabilities for bit “0” and “1” are different during each round of evolution in the decoding process. We refer to this property as asymmetrical recovery. To authors’ best knowledge, this paper is the first one to formulate CS decoding by taking the asymmetrical recovery into account. With the new formulation, the recursion of unrecoverable probability of source bits can be characterized more precisely than previous formulations. Furthermore, as an important property of CS decoding, we also characterize the variation on asymmetrical recovery in different rounds of evolution. The simulation results show that the new formulation has a close match with the actual decoding. Finally, we derive design guidelines for random sensing matrices from the source coding perspective. an>

Short Bio: