Coded fourier transform

Qian Yu, Mohammad Ali Maddah-Ali, A. Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

35 Scopus citations

Abstract

We consider the problem of computing the Fourier transform of high-dimensional vectors, distributedly over a cluster of machines consisting of a master node and multiple worker nodes, where the worker nodes can only store and process a fraction of the inputs. We show that by exploiting the algebraic structure of the Fourier transform operation and leveraging concepts from coding theory, one can efficiently deal with the straggler effects. In particular, we propose a computation strategy, named as coded FFT, which achieves the optimal recovery threshold, defined as the minimum number of workers that the master node needs to wait for in order to compute the output. This is the first code that achieves the optimum robustness in terms of tolerating stragglers or failures for computing Fourier transforms. Furthermore, the reconstruction process for coded FFT can be mapped to MDS decoding, which can be solved efficiently. Moreover, we extend coded FFT to settings including computing general n-dimensional Fourier transforms, and provide the optimal computing strategy for those settings.

Original languageEnglish (US)
Title of host publication55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages494-501
Number of pages8
ISBN (Electronic)9781538632666
DOIs
StatePublished - Jul 1 2017
Externally publishedYes
Event55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017 - Monticello, United States
Duration: Oct 3 2017Oct 6 2017

Publication series

Name55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Volume2018-January

Other

Other55th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2017
Country/TerritoryUnited States
CityMonticello
Period10/3/1710/6/17

Bibliographical note

Funding Information:
This work is in part supported by NSF grant CIF 1703575, ONR award N000141612189, and a research gift from Intel. This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.

Publisher Copyright:
© 2017 IEEE.

Fingerprint

Dive into the research topics of 'Coded fourier transform'. Together they form a unique fingerprint.

Cite this