```
Released a simple Matlab version of a sublinear sparse Fourier transform. https://t.co/uzJNzyFzHK
— Anna C Gilbert (@annacgilbert) October 13, 2015
```

Awesome ! I met Anna back in 2008 at Texas A&M University in what proved to be the beginning of many things in my mind and on this blog. I am proud to say that the 400th implementation made available by a researcher of an algorithm and listed here is that of Anna. It is on this Github page:

## Simple-sublinear-Fourier-sampling

This library of matlab code provides a very simple implementation of a sublinear Fourier sampling algorithm. This is not the fastest algorithm or implementation, nor is it the most sophisticated, but it is an example of a straightforward sublinear time algorithm.

It is modeled on A. C. Gilbert ; S. Muthukrishnan and M. Strauss, "Improved time bounds for near-optimal sparse Fourier representations", Proc. SPIE 5914, Wavelets XI, 59141A (May 04, 2011); doi:10.1117/12.615931; http://dx.doi.org/10.1117/12.615931.

Files included are

The driver file is

- estimate_coeffs.m
- eval_sig.m
- fourier_sampling.m
- generate_sample_set.m
- generate_signal.m
- generate_tspairs.m
- identify_frequencies.m
- sample_residual.m
- sample_shattering.m
- test_AAFFT_with_presampling.m
test_AAFFT_with_presampling.mAt the top of this file, you set up the signal and all of its parameters (length, number of tones, and total l2 norm of the additive white noise, if there is any). The functiongenerate_signal.msets up a data structure for the signal. It doesnotgenerateallof the signal values as this would be a wasteful procedure! Next, you set up the parameters of the AAFFT algorithm. Please see the comments for reasonable values.generate_tspairs.mgenerates the pairs of random numbers for the random arithmetic progressions while the code ingenerate_sample_set.mactually generates the indices at which we sample the signal. There are two different sampling sets,samp1andsamp2; one for identification and one for estimation. Note that they are structured differently. Also, if you want to visualize just what indices are sampled, you can plot these sets. The variablesxs1andxs2contain the actual sample values. Note that we actually compute the signal at these sample points rather than sampling from a large vector (more space-efficient). The functionfourier_sampling.mdoes all of the important work and returns a data structure containing frequencies and their associated coefficients. The last lines of the driver file compute the error of the returned representation.

**Image Credit: NASA/JPL-Caltech/Space Science Institute**

Full-Res: N00249257.jpg

N00249257.jpg was taken on October 11, 2015 and received on Earth October 12, 2015. The camera was pointing toward RHEA, and the image was taken using the RED and CL2 filters.

**Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !**

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

## No comments:

Post a Comment