Hard Thresholding based Stochastic Algorithm for Distributed Sparse Recovery

In this paper, we consider a diffusion network with the objective of minimizing a cost function at each node by a global optimizer, assumed to be K-sparse, by utilizing diffusion based collaboration among the nodes. In the proposed algorithm termed as DiffstoHT here, in each iteration, first a stochastic gradient based update is calculated followed by K level hard thresholding at each node. The resulting estimates are then shared with the neighbors of the node by means of diffusion and subsequently a weighted linear combination of the incoming estimates is taken followed by 2K level hard thresholding. Next, each node carries out certain gradient descent iterations sequentially, restricted to the 2K-sized support obtained from previous stage. Lastly, another K level hard thresholding is performed by each node, completing one iteration. The proposed DiffStoHT algorithm is particularly useful for large scale problems where full gradient calculation is expensive. Theoretical analysis of the proposed DiffStoHT algorithm is carried out using the restricted positive definite Hessian (RPDH) property of the cost functions and sufficient conditions for recovery are derived. Simulations suggest that the proposed algorithm is not only faster than existing diffusion based methods, but it is also capable of outperforming them in terms of probability of recovery.