Exploring connections between Sparse Fourier Transform computation and decoding of product codes
- Additional Document Info
- View All
2015 IEEE. We show that the recently proposed Fast Fourier Aliasing-based Sparse Transform (FFAST) algorithm for computing the Discrete Fourier Transform (DFT)  of signals with a sparse DFT is equivalent to iterative hard decision decoding of product codes. This connection is used to derive the thresholds for sparse recovery based on a recent analysis by Justensen  for computing thresholds for product codes. We first extend Justesen's analysis to d-dimensional product codes and compute thresholds for the FFAST algorithm based on this. Additionally, this connection also allows us to analyze the performance of the FFAST algorithm under a burst sparsity model in addition to the uniformly random sparsity model which was assumed in prior work .
name of conference
2015 53rd Annual Allerton Conference on Communication, Control and Computing (Allerton)
2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)
author list (cited authors)
Janakiraman, N. T., Emmadi, S., Narayanan, K., & Ramchandran, K.
complete list of authors
Janakiraman, Nagaraj Thenkarai||Emmadi, Santosh||Narayanan, Krishna||Ramchandran, Kannan