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

22 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’ve been browsing on-line greater than three hours today, but I never discovered any attention-grabbing article like yours. It is beautiful worth sufficient for me. Personally, if all webmasters and bloggers made good content material as you did, the net will be a lot more helpful than ever before.

    SMO Services Chennai

    ReplyDelete
    Replies
    1. I have read your blog its very attractive and impressive. I like it your blog.

      Digital Marketing Company in Chennai Digital Marketing Agency

      Delete
  7. 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
  8. Great information shared in this blog. Helps in gaining concepts about new information and concepts.Awsome information provided.Very useful for the beginners.
    SEO Training in Chennai

    ReplyDelete
  9. 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
  10. 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
  11. It's interesting that many of the bloggers to helped clarify a few things for me as well as giving.Most of ideas can be nice content.The people to give them a good shake to get your point and across the command.

    Digital Marketing Course in Chennai

    ReplyDelete
  12. Great post!I am actually getting ready to across this information,i am very happy to this commands.Also great blog here with all of the valuable information you have.Well done,its a great knowledge.
    New Zealand Education Consultants in Chennai

    ReplyDelete
  13. 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
  14. 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.

    Fresher Jobs in Mumbai
    Fresher Jobs in Pune
    Fresher Jobs in Noida
    Fresher Jobs in Hyderabad

    ReplyDelete
  15. 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
  16. I am not sure the place you are getting your information, however good topic.I needs to spend some time studying more or understanding more.Thank you for wonderful information I was in search of this info for my mission.

    Manpower Consultancy in Bangalore
    HR Consultancy in Bangalore
    Recruitment Consultancy in Bangalore
    HR Franchise in Bangalore

    ReplyDelete
  17. 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


  18. This information is impressive; I am inspired with your post writing style & how continuously you describe this topic.

    Payday loans in Alabama
    Title loans in South Carolina

    ReplyDelete
  19. I’m sincerely suggesting your blog to all my friends… I’ve changed myself in many thing after reading your blog… Thanks and keep going.
    Best Interior Designers in Chennai
    Interior Designers in Chennai

    ReplyDelete

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