Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloRandomized Algorithms for Distributed Nonlinear Optimization Under Sparsity Constraints
Anno di pubblicazione2016
Autore/iRavazzi, Chiara; Fosson, Sophie M.; Magli, Enrico
Affiliazioni autoriPolitecnico di Torino
Autori CNR e affiliazioni
  • inglese
AbstractDistributed optimization in multi-agent systems under sparsity constraints has recently received a lot of attention. In this paper, we consider the in-network minimization of a continuously differentiable nonlinear function which is a combination of local agent objective functions subject to sparsity constraints on the variables. A crucial issue of in-network optimization is the handling of the communications, which may be expensive. This calls for efficient algorithms, that are able to reduce the number of required communication links and transmitted messages. To this end, we focus on asynchronous and randomized distributed techniques. Based on consensus techniques and iterative hard thresholding methods, we propose three methods that attempt to minimize the given function, promoting sparsity of the solution: asynchronous hard thresholding (AHT), broadcast hard thresholding (BHT), and gossip hard thresholding (GHT). Although similar in many aspects, it is difficult to obtain a unified analysis for the proposed algorithms. Specifically, we theoretically prove the convergence and characterize the limit points of AHT in regular networks under some proper assumptions on the functions to be minimized. For BHT and GHT, instead, we characterize the fixed points of the maps that rule their dynamics in terms of stationary points of original problem. Finally, we illustrate the implementation of our techniques in compressed sensing and present several numerical results on performance and number of transmissions required for convergence.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da1420
Pagine a1434
Pagine totali15
RivistaIEEE transactions on signal processing
Attiva dal 1991
Editore: Institute of Electrical and Electronics Engineers, - New York, NY
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 1053-587X
Titolo chiave: IEEE transactions on signal processing
Titolo proprio: IEEE transactions on signal processing
Titolo abbreviato: IEEE trans. signal process.
Titoli alternativi:
  • Institute of Electrical and Electronics Engineers transactions on signal processing
  • Transactions on signal processing
  • Signal processing
Numero volume della rivista64
Fascicolo della rivista6
Verificato da refereeSì: Internazionale
Stato della pubblicazionePostprint
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000372003500005)
Parole chiaveDistributed optimization, nonlinear optimization, randomized algorithms, sparse signal recovery
Link (URL, URI)-
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR-
Progetti Europei
  • Randomized Algorithms for Distributed Nonlinear Optimization Under Sparsity Constraints
    Descrizione: PDF