CaltechAUTHORS
  A Caltech Library Service

Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus

Azizan-Ruhi, Navid and Lahouti, Farshad and Avestimehr, Salman and Hassibi, Babak (2018) Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus. In: 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE , Piscataway, NJ, pp. 6358-6362. ISBN 978-1-5386-4658-8. https://resolver.caltech.edu/CaltechAUTHORS:20180920-110215437

[img] PDF - Submitted Version
See Usage Policy.

520kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180920-110215437

Abstract

Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus (APC) for this problem. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative distributed methods, namely distributed gradient descent, distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and ADMM. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ICASSP.2018.8462630DOIArticle
https://arxiv.org/abs/1708.01413arXivDiscussion Paper
http://resolver.caltech.edu/CaltechAUTHORS:20190610-092256233Related ItemJournal Article
ORCID:
AuthorORCID
Azizan-Ruhi, Navid0000-0002-4299-2963
Lahouti, Farshad0000-0002-8729-873X
Additional Information:© 2018 IEEE.
Subject Keywords:System of linear equations, distributed computing, big data, consensus, optimization
DOI:10.1109/ICASSP.2018.8462630
Record Number:CaltechAUTHORS:20180920-110215437
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20180920-110215437
Official Citation:N. Azizan-Ruhi, F. Lahouti, S. Avestimehr and B. Hassibi, "Distributed Solution of Large-Scale Linear Systems Via Accelerated Projection-Based Consensus," 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Calgary, AB, Canada, 2018, pp. 6358-6362. doi: 10.1109/ICASSP.2018.8462630
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89783
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:20 Sep 2018 18:22
Last Modified:16 Nov 2021 00:38

Repository Staff Only: item control page