Tuesday, October 13, 2015

Simple sublinear Fourier sampling , the 400th implementation.

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:


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
  • 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
The driver file is test_AAFFT_with_presampling.m At 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 function generate_signal.m sets up a data structure for the signal. It does not generate all of 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.m generates the pairs of random numbers for the random arithmetic progressions while the code in generate_sample_set.m actually generates the indices at which we sample the signal. There are two different sampling sets, samp1 and samp2; 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 variables xs1 and xs2 contain 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 function fourier_sampling.m does 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: