Efficient decentralized approximation via selective gossip

Abstract—Recently, gossip algorithms have received much atten-tion from the wireless sensor network community due to their sim-plicity, scalability and robustness. Motivated by applications such as compression and distributed transform coding, we propose a new gossip algorithm called Selective Gossip. Unlike traditional randomized gossip which computes the average of scalar values, we run gossip algorithms in parallel on the elements of a vector. The goal is to compute only the entries which are above a defined threshold in magnitude, i.e., significant entries. Nodes adaptively approximate the significant entries while abstaining from calcu-lating the insignificant ones. Consequently, network lifetime and bandwidth are preserved. We show that with the proposed algo-rithm nodes reach consensus on the values of the significant entries and on the indices of insignificant ones. We illustrate the perfor-mance of our algorithm with a field estimation application. For reg-ular topologies, selective gossip computes an approximation of the field using the wavelet transform. For irregular network topologies, we construct an orthonormal transform basis using eigenvectors of the graph Laplacian. Using two real sensor network datasets we show substantial communication savings over randomized gossip. We also propose a decentralized adaptive threshold mechanism such that nodes estimate the threshold while approximating the en-tries of the vector for computing the best-term approximation of the data. Index Terms—Distributed algorithms, field estimation, sparse approximation, wireless sensor networks. I