Monday, August 24, 2015

The FFT is Fifty


Their 1965 paper starts with the unassuming words "An efficient method for the calculation of the interactions of a 2^m factorial experiment was introduced by Yates and is widely known by his name." The paper does not use the word "fast" even once. But the algorithm described in that paper written by James Cooley and John Tukey[1] came to be known as the Fast Fourier Transform (FFT), and turned out to be just what the world was waiting for. Overnight, in universities and laboratories around the world, scientists and engineers began writing code and building hardware to implement the FFT. Fifty years later, versions of that algorithm are routinely used, often tacitly assumed to be available to programmers. Any computation that requires (either as an end, or as an intermediate step) the unraveling of the frequency content of information carrying signals benefits from the enormous speedup offered by the FFT. Other than the speedup, the FFT does not offer any computational result that was not available before its discovery. However, were it not for this amazing algorithm, it would be practically impossible to filter cell-phone signals, to compress movie files, do spectroscopy, take magnetic resonance imaging scans, perform quantum computing, and solve differential equations, among other things. The Cooley-Tukey paper created a surge in products that suddenly became possible, and often even became practical to operate in real-time.
Although the idea behind FFT can be explained without using complex math (it involves complex numbers, so I guess that does make the math complex), no attempt to do so will be made here. Suffice it to say that the algorithm belongs to a class of mathematical calculations that can either be performed in a straightforward manner, or can be solved by dividing the calculations into smaller steps. Cooley and Tukey showed how the dividing could be done in a manner such that the total effort needed to compute the simpler steps is much less than the effort that would be needed to tackle the computation without such division. There is a wealth of deep mathematics underlying the FFT algorithm. But let us remember that John Tukey, ever the pragmatic engineer, is said to have declared “I wouldn’t want to fly in a plane whose design depended on whether a function was Riemann or Lebesgue integrable.”
For signals with a million samples, the gain in speed obtained by virtue of the magic of FFT can be upwards of 50,000. To appreciate this speedup ratio, consider some calculation that takes 1 second to complete on your computer. To most of us, this would seem sluggish. In today's world we expect our devices to be instantly responsive, but we might tolerate such slowness once in a while, say when we are applying some fancy effects to produce an irresistible cat video. Now, imagine that same computation being 50,000 times slower i.e. taking almost 14 hours to execute.
For decades, the FFT algorithm and its direct variants have ruled the world of signal processing. It is only recently that researchers[2]  at MIT came up with an algorithm which takes advantage of a special property of real-life signals (sparsity) to achieve significantly faster performance. Although the speedup achieved (relative to the FFT, not relative to the straightforward computation) is not as spectacular, it is still useful in many practical applications. For example, it has the potential to reduce the time patients spend inside a MRI machine from an agonizing one hour to a bearable 20 minutes. There are many other applications where increased efficiency of computing the spectrum leads to other benefits such as longer battery life.
My introduction to the FFT came via a classic textbook, Athanasios Papoulis's Signal Analysis. In graduate school, I remember scribbling pages after pages of formulas as I worked to absorb the concept. When it all fell into place, the feeling was as exhilarating as though I had personally come up with the algorithm myself. Wonderful applications suggested themselves, and it seemed that the world could be saved by my new found understanding of the FFT.
I was to be humbled because I was soon introduced to an application made possible by the FFT. Transmultiplexers are computational devices that allow a single wire (or radio channel) to simultaneously transmit thousands of speech signals in a way that allows them to be separated by individual receivers. Remarkably, FFT figures into the calculations needed to pull off this feat. Unlike common applications I had encountered at that time where the input to the FFT is a sequence of samples of a single signal as it is generated in time, in the transmultiplexer calculations, the input to the FFT at each time step is the sequence formed by gathering samples of several independent speech signals at a given instant of time. It amazed me that you could, in a manner of speaking, meaningfully combine and take apart independent words uttered by a crowd at a given time instant. Now this is one application I could not have come up with.
I know that many engineers and scientists have their own personal story of their first encounter with the FFT. Well, we are nerds are we not? Can we share?
------------
[1] Cooley, James W.; Tukey, John W. (1965). "An algorithm for the machine calculation of complex Fourier series". Mathematics of Computation, 19: 297–301.
[2] Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price. (2012). "Simple and Practical Algorithm for Sparse Fourier Transform". ACM-SIAM Symposium on Discrete Algorithms, Kyoto Japan

33 comments:

  1. A very nice article. I now know so many things about this topic.

    ReplyDelete
  2. Very nicely written. Is there any field which Tukey has left untouched :-)

    ReplyDelete
  3. Usually I do not read post on blogs, but I would like to say that this write-up very forced me to try and do it! Your writing style has been surprised me. Thanks, very nice article.

    Linux Training in Chennai Guindy

    ReplyDelete
  4. This comment has been removed by a blog administrator.

    ReplyDelete
  5. All are saying the same thing repeatedly, but in your blog I had a chance to get some useful and unique information, I love your writing style very much, I would like to suggest your blog in my dude circle, so keep on updates.


    Digital Marketing Company in Chennai

    ReplyDelete
  6. I am expecting more interesting topics from you. And this was nice content and definitely it will be useful for many people.

    Digital Marketing For Small Business in Chennai

    ReplyDelete
  7. I think this is interesting articles and Business ethics for new information's, and i like that kind of information.So the i like that post,because all of given information was very excellent

    Informatica Training in Chennai

    ReplyDelete
  8. keep sharing your information regularly for my future reference. This content creates a new hope and inspiration with in me


    Best Dot Net Training Institutes in Chennai

    ReplyDelete
  9. Truely a very good article on how to handle the future technology. After reading your post,thanks for taking the time to discuss this, I feel happy about and I love learning more about this topic.keep sharing your information regularly for my future reference

    Best Dental Clinic In Vellore

    ReplyDelete
  10. Great post! I am actually getting ready to across this information, It's very helpful for this blog.Also great with all of the valuable information you have Keep up the good work you are doing well.
    Manpower Services in Chennai

    ReplyDelete
  11. reat post! I am actually getting ready to across this information, It's very helpful for this blog.Also great with all of the valuable information you have Keep up the good work you are doing well.

    Digital Marketing Company in Chennai

    ReplyDelete
  12. This comment has been removed by the author.

    ReplyDelete
  13. This blog is having the general information. Got a creative work and this is very different one.We have to develop our creativity mind.This blog helps for this.Thank you for this blog.This is very interesting and useful.

    Self Employment Tax
    TaxPreparation Services
    Tax Accountant
    Tax Consultant
    Tax Advisor

    ReplyDelete
  14. This comment has been removed by the author.

    ReplyDelete
  15. The Car featured content undergoes a thorough review process to ensure that it meets the highest standards in order to serve as the best car spare parts and fit the goals.

    Car Accessories in OMR

    ReplyDelete

  16. I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post. I hope I will see again.
    Deer Hunting Tips Camping Trips Guide DEER HUNTING TIPS travel touring tips

    ReplyDelete

  17. I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post. I hope I will see again.
    Still Hunting Method
    Hunting psych tips Survival Tips Travel Touring Tips

    ReplyDelete

  18. I enjoyed over read your blog post. Your blog have nice information, I got good ideas from this amazing blog. I am always searching like this type blog post. I hope I will see again.
    travel trekking tips
    see the link Tent Camping 101 Exploring Smithriver

    ReplyDelete
  19. Itu merupakan cara bermain dalam ceme online, gampang bukan? mungkin hanya 5 menit saja permainan itu sudah selesai.
    asikqq
    dewaqq
    sumoqq
    interqq
    pionpoker
    bandar ceme terbaik
    hobiqq
    paito warna
    forum prediksi

    ReplyDelete
  20. I really like your writing style, great date, thank you for posting.
    https://360digitmg.com/course/project-management-professional-pmp

    ReplyDelete
  21. incredible article!! sharing these kind of articles is the decent one and I trust you will share an article on information science.By giving an organization like 360DigiTMG.it is one the best foundation for doing guaranteed courses
    data scientist malaysia

    ReplyDelete
  22. This is a great motivational article. In fact, I am happy with your good work. They publish very supportive data, really. Continue. Continue blogging. Hope you explore your next post
    what is hrdf

    ReplyDelete
  23. Regular visits listed here are the easiest method to appreciate your energy, which is why why I am going to the website everyday, searching for new, interesting info. Many, thank you!
    business analytics course

    ReplyDelete
  24. Nice Blog !
    Amid the chaos and negativity, we at QuickBooks Customer Service Number 1-855-974-6537 offer genuine help and support for QuickBooks in the least possible time.

    ReplyDelete
  25. Impressive. Your story always brings hope and new energy. Keep up the good work.

    Data Science Training in Hyderabad

    ReplyDelete
  26. Your work is very good and I appreciate you and hopping for some more informative posts
    data scientist certification malaysia

    ReplyDelete
  27. I am genuinely thankful to the holder of this web page who has shared this wonderful paragraph at this place
    full stack web development course


    ReplyDelete
  28. Get the answer for the query “ How To Get a Job in Infosys as a Fresher? ” with the real-time examples and best interview questions and answers from the best software training institute in Chennai, Infycle Technologies. Get the best software training and placement with the free demo and great offers, by calling +91-7504633633, +91-7502633633.

    ReplyDelete

I welcome your comments. Do let me know if you have a numerical and insightful story to tell.