TY - GEN
T1 - Sample-optimal average-case sparse Fourier Transform in two dimensions
AU - Ghazi, Badih
AU - Hassanieh, Haitham
AU - Indyk, Piotr
AU - Katabi, Dina
AU - Price, Eric
AU - Shi, Lixin
PY - 2013
Y1 - 2013
N2 - We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional √n × √n grid. Our algorithms are analyzed for the average case signals. For signals whose spectrum is exactly sparse, we present algorithms that use O(k) samples and run in O(k log k) time, where k is the expected sparsity of the signal. For signals whose spectrum is approximately sparse, we have an algorithm that uses O(k log n) samples and runs in O(k log2 n) time, for k = Θ(√n). All presented algorithms match the lower bounds on sample complexity for their respective signal models.
AB - We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional √n × √n grid. Our algorithms are analyzed for the average case signals. For signals whose spectrum is exactly sparse, we present algorithms that use O(k) samples and run in O(k log k) time, where k is the expected sparsity of the signal. For signals whose spectrum is approximately sparse, we have an algorithm that uses O(k log n) samples and runs in O(k log2 n) time, for k = Θ(√n). All presented algorithms match the lower bounds on sample complexity for their respective signal models.
UR - http://www.scopus.com/inward/record.url?scp=84897734712&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84897734712&partnerID=8YFLogxK
U2 - 10.1109/Allerton.2013.6736670
DO - 10.1109/Allerton.2013.6736670
M3 - Conference contribution
AN - SCOPUS:84897734712
SN - 9781479934096
T3 - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
SP - 1258
EP - 1265
BT - 2013 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
PB - IEEE Computer Society
T2 - 51st Annual Allerton Conference on Communication, Control, and Computing, Allerton 2013
Y2 - 2 October 2013 through 4 October 2013
ER -