Sparse Fourier Transforms – Experiments

Exactly sparse data

In order to generate a random sparse signal, we pick a support of size k uniformly at random. Then, we set the supported coefficients to 1 and the remaining coefficients to 0.

Runtime vs signal length

In the following experiments, the sparsity parameter k is set to 50 for all values of N.

Runtime vs sparsity

In the following experiments, the signal length N is set to 2^22 for all values of k.

Approximately sparse data

In order to generate a random sparse signal, we proceed in two stages. First, we pick a support of size k uniformly at random. We set the supported coefficients to a complex number with unit norm and phase chosen uniformly at random. The remaining coefficients are set to 0. Second, we add i.i.d. Gaussian noise to each coefficient. The variance is chosen so that we achieve a certain SNR.

Runtime vs signal length

In the following experiments, the sparsity parameter k is set to 50 for all values of N. The SNR is set to 20 dB.

Runtime vs sparsity

In the following experiments, the signal length N is set to 2^22 for all values of k. The SNR is set to 20 dB.

Experiment setup

All experiments were conducted on a computer with a Intel Core i7 CPU (M 620) running at 2.67 GHz. The system has a total of 6 MB CPU cache and 8 GB RAM. We obtained timing information with the UNIX function clock_gettime(), using the Linux-specific timer CLOCK_MONOTONIC_RAW.

For all data points, we generated 10 random inputs with corresponding parameters and used the same inputs for all algorithms. Each algorithm was run on each input 10 times. We then average the results in order to get the corresponding data point. The error bars indicate the range from 0th to 95th percentile.