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 .
author list (cited authors)
Janakiraman, N. T., Emmadi, S., Narayanan, K., & Ramchandran, K.