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
![]() |
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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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