  We present a novel algorithm, named the 2D-FFAST, to compute a sparse
2D-Discrete Fourier Transform (2D-DFT) featuring both low sample complexity and
low computational complexity. The proposed algorithm is based on mixed concepts
from signal processing (sub-sampling and aliasing), coding theory (sparse-graph
codes) and number theory (Chinese-remainder-theorem) and generalizes the
1D-FFAST 2 algorithm recently proposed by Pawar and Ramchandran [1] to the 2D
setting. Concretely, our proposed 2D-FFAST algorithm computes a k-sparse
2D-DFT, with a uniformly random support, of size N = Nx x Ny using O(k)
noiseless spatial-domain measurements in O(k log k) computational time. Our
results are attractive when the sparsity is sub-linear with respect to the
signal dimension, that is, when k -> infinity and k/N -> 0. For the case when
the spatial-domain measurements are corrupted by additive noise, our 2D-FFAST
framework extends to a noise-robust version in sub-linear time of O(k log4 N )
using O(k log3 N ) measurements. Simulation results, on synthetic images as
well as real-world magnetic resonance images, are provided in Section VII and
demonstrate the empirical performance of the proposed 2D-FFAST algorithm.
