Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Faster Fourier transform among world’s most important emerging technology

web.mit.edu

Post reply on HN
Print view View original

31–40 of 49 posts

Re: Faster Fourier transform among world’s most important emerging technology

#31

Post by moultano »

maaku wrote: post #17
dustingetz wrote: post #14

they make this seem like a huge deal, anyone know why? is this going to like put HD content on an iPhone? I don't expect that the signal processing hardware is the bottleneck here.

> I don't expect that the signal processing hardware is the bottleneck here. Computational resources is always the bottleneck in bioinformatics, quantum chemistry, or any sort of high data volume analysis or simulation, and the FFT is a fundamental and commonly used transform in all fields. At least for people who still use computers to, well, compute things, a faster FFT is a huge deal.

How many domains still use FFT specifically though as opposed to some other transform? Most of the signal processing papers of the last decade that I've read or read about have used either wavelets, FFT on a small window such that this isn't really applicable, or some arbitrary non-orthogonal basis.

Re: Faster Fourier transform among world’s most important emerging technology

#32

Post by KingMob »

moultano wrote: post #31
maaku wrote: post #17

Earlier quoted context omitted.

> I don't expect that the signal processing hardware is the bottleneck here. Computational resources is always the bottleneck in bioinformatics, quantum chemistry, or any sort of high data volume analysis or simulation, and the FFT is a fundamental and commonly used transform in all fields. At least for people who still use computers to, well, compute things, a faster FFT is a huge deal.

How many domains still use FFT specifically though as opposed to some other transform? Most of the signal processing papers of the last decade that I've read or read about have used either wavelets, FFT on a small window such that this isn't really applicable, or some arbitrary non-orthogonal basis.

When I was doing EEG signal analysis in grad school, I used the FFT all the time. While there's some cool stuff involving wavelets and using interesting basis sets (matching pursuit looks cool), if you're primarily looking at power and frequency over time, the FFT is sufficient, and usually faster than the other algorithms. (And if you're looking at power/phase, the common Morlet wavelet choice is mathematically equivalent to an FT with a Gaussian taper.)

I'm not sure what you mean by "on a small window such that this isn't really applicable"; can you give an example? As long as you accept the inherent time-frequency resolution trade-offs, there's no obstacle to using FFT on a small window. It's called the short-time Fourier transform (STFT), and it's used everywhere; it's probably used more than analyzing an entire signal, since we frequently want to know how power and phase change over time in a signal, and a full-signal FT can't tell you that.

Re: Faster Fourier transform among world’s most important emerging technology

#33

Post by moultano »

KingMob wrote: post #32
moultano wrote: post #31

Earlier quoted context omitted.

How many domains still use FFT specifically though as opposed to some other transform? Most of the signal processing papers of the last decade that I've read or read about have used either wavelets, FFT on a small window such that this isn't really applicable, or some arbitrary non-orthogonal basis.

When I was doing EEG signal analysis in grad school, I used the FFT all the time. While there's some cool stuff involving wavelets and using interesting basis sets (matching pursuit looks cool), if you're primarily looking at power and frequency over time, the FFT is sufficient, and usually faster than the other algorithms. (And if you're looking at power/phase, the common Morlet wavelet choice is mathematically equi…

>I'm not sure what you mean by "on a small window such that this isn't really applicable"

FFT is very useful on a small window, but algorithms that improve the asymptotic efficiency are unlikely to be useful at that scale. With n=100 the asymptote doesn't matter. We'll still be using the FFT forever, I'm just skeptical that the frontiers of technology will be advanced by a faster FFT, since it seems like the coolest stuff is happening elsewhere. It's increasingly becoming the quick-and-dirty counterpart to the sophisticated-but-slow methods.

Re: Faster Fourier transform among world’s most important emerging technology

#34

Post by kleiba »

I just had a somewhat closer look at the MIT Technology review list of emerging technologies, and in particular the people behind them. I made a rather sad discovery. Please take a look at the following list:

- Jonathan Tilly (stem cell research)

- John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders)

- Ren Ng (light field photography, Lytro founder)

- Nikhil Jaisinghani, Brian Shaad (solar-powered microgrids, Mera Gao Power founders)

- Mark Bohr (3D transistors, head of Intel's process technology)

- Piotr Indyk, Dina Katabi, Eric Price, Haitham Hassanieh (Sparse Fourier transform)

- Gordon Sanghera, Spike Willcocks, Hagan Bayley (DNA sequencing, Oxford Nanopore founders)

- Perry Chen, Yancey Strickler, Charles Adler (Kickstarter founders)

- Peter Schultz, Robert Downs, Donald Murphy (Wildcat Discovery Technologies founders)

- Mark Zuckerberg (Facebook founder)

This is the list of the people behind all of the ten emerging technologies, as listed on http://www.technologyreview.com/tr10/

  Number of people on the list: 23
  Number of women on the list:  1
At least for Intels 3D transistor team and Facebook's timeline, I was not able to dig up the list of people on the team who develop these technologies, so there is still some hope that there are a few more women on these teams at least. The same should hold for the research on egg stem cell research.

Re: Faster Fourier transform among world’s most important emerging technology

#35

Post by jpeg_hero »

kleiba wrote: post #34

I just had a somewhat closer look at the MIT Technology review list of emerging technologies, and in particular the people behind them. I made a rather sad discovery. Please take a look at the following list: - Jonathan Tilly (stem cell research) - John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders) - Ren Ng (light field photography, Lytro founder) - Nikhil Jaisinghani, Brian Shaad (…

Are you disappointed because women are not contributing to "breakthrough technologies" or do you think there were worthwhile women that were overlooked?

Re: Faster Fourier transform among world’s most important emerging technology

#36

Post by rhino42 »

jpeg_hero wrote: post #35
kleiba wrote: post #34

I just had a somewhat closer look at the MIT Technology review list of emerging technologies, and in particular the people behind them. I made a rather sad discovery. Please take a look at the following list: - Jonathan Tilly (stem cell research) - John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders) - Ren Ng (light field photography, Lytro founder) - Nikhil Jaisinghani, Brian Shaad (…

Are you disappointed because women are not contributing to "breakthrough technologies" or do you think there were worthwhile women that were overlooked?

Highly relevant question. As someone with a signal processing background, the SFT is so huge that without doubt it should be on this list. Knowing MIT's meritocracy, they would have given the award to more women if it were appropriate

Re: Faster Fourier transform among world’s most important emerging technology

#37

Post by kleiba »

jpeg_hero wrote: post #35
kleiba wrote: post #34

I just had a somewhat closer look at the MIT Technology review list of emerging technologies, and in particular the people behind them. I made a rather sad discovery. Please take a look at the following list: - Jonathan Tilly (stem cell research) - John A. Rogers, Ralph Nuzzo, George M. Whitesides, Etienne Menard (Semprius founders) - Ren Ng (light field photography, Lytro founder) - Nikhil Jaisinghani, Brian Shaad (…

Are you disappointed because women are not contributing to "breakthrough technologies" or do you think there were worthwhile women that were overlooked?

I'm basically just stating the fact, leaving an interpretation open for everyone who's interested.

A while ago, there were a few front page posts about the role of women in IT, and about how they find themselves in their work environments. The MIT list is not restricted to computer science, but perhaps it can be interpolated to the relevant fields here, too?

I think it stands out that women are heavily under-represented on this list, and although explanations for that fact might be manifold, I personally just find it a bit sad to look at that outcome.

Re: Faster Fourier transform among world’s most important emerging technology

#38

Post by joshma »

mturmon wrote: post #7
ihodes wrote: post #5

Paper at: http://arxiv.org/abs/1201.2501v1 O(k log n log(n/k)) complexity for the general case.

...where k is the number of FFT coefficients computed, and n is the time series length. Has anyone else been turned off by the sensationalism of MIT TR articles?

With all due respect, this is anything but sensationalism. It might help to understand that the number of FFT coefficients computed is not necessarily the number of data points processed. Theoretically, if we have a perfect cosine, for example, we'd get TWO non-zero coefficients (k=2) even if n was a huge number. Compare O(k logn log(n/k)) to O(nlogn) in those cases!

Granted, this doesn't apply to every single situation. However, citing the article in the case of video signals, you have on average 7 "non-negligible" coefficients (k~7). So there are certainly applications that will benefit dramatically from this.

Re: Faster Fourier transform among world’s most important emerging technology

#39

Post by wissler »

This is not a "faster" FFT. It's not a FFT at all.

"Because the SFT algorithm isn't intended to work with all possible streams of data, it can take certain shortcuts not otherwise available. In theory, an algorithm that can handle only sparse signals is much more limited than the FFT."

It may well be a very useful algorithm that does FFT-like operations, but the title is marketing hype and it's impossible to judge the true range of applicability of this algorithm from the article alone.

Re: Faster Fourier transform among world’s most important emerging technology

#40

Post by Jimmie »

guelo wrote: post #15
moldbug wrote: post #8

Awesome. It'll sure be nifty when 2029 rolls around and the patent expires, so applications can actually use the algorithm. (No, I don't have any information that an sFFT patent has been filed, but this would be standard practice at MIT). Tornado/fountain codes are a similar case. Pardon my bitterness, but it's an interesting question to wonder whether, by funding researchers to invent algorithms of this type and loc…

Algorithms and mathematical methods are not supposed to be patentable in the US.

The "Marching Cubes"[1] algorithm got patented ages ago and the patent was enforced. Some clever people had to come up with a similar solution called "Marching Tetrahedrons" to work around the patent.

[1]http://en.wikipedia.org/wiki/Marching_cubes

Post reply on HN