Decentralized Joint Sparse Optimization

Introduction

A set of vectors are jointly sparse if their nonzeros are restricted to a common, small subset of locations.

Decentralized joint sparse optimization is suitable for a network of distributed nodes to obtain joint sparse vectors without a fusion center, or without sending their data to the fusion center for processing.

Decentralized computation

Decentralized computation is distributed computation without a center. Removing any computing node will not affect the remaining nodes as long as they stay connected.

Model

A connected network has L nodes, and each node i, i=1,2,...,L, wants to recover x⁽ⁱ⁾ from its data y⁽ⁱ⁾. The set of vectors {x⁽ⁱ⁾} is jointly sparse. We recover {x⁽ⁱ⁾} by solving

where g⁽ⁱ⁾ is the data fidelity function of node i, f is a regularization function which tends to be small when its input are joint sparse, and λ is a weight parameter.

An example with linear least-squares fidelity and non-convex regularization function is

where q=1 or 2 and ε_q is a smoothing parameter. This model can be used for compressive sensing recovery of joint sparse signals.

A decentralized algorithm for solving this model is given in

• Q. Ling, Z. Wen, and W. Yin, Decentralized Jointly Sparse Recovery by Reweighted L_q Minimization.

Software

Demo version 1.0 (Mar 29, 2012).

Feedback

Qing Ling, Zaiwen Wen, and Wotao Yin would be happy to hear from you if you find the proposed method useful, or if you have any suggestions, contributions, or bug reports.

Ackowledgements

The work of Q. Ling was supported in part by NSFC 61004137. The work of W. Yin was supported in part by NSF DMS-07-48839 and ECCS-1028782, ONR N00014-08-1-1101, U.S. ARL and ARO W911NF-09-1-0383.