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 lock them away behind a patent-wall for two decades, USG is advancing the progress of technology or in fact retarding it.
Mathematical facts aren't patentable. That much has been established. Perhaps a "pure" algorithm isn't patentable; but all software patents start out with something like "a general purpose computer which...", tying it to hardware and making it patentable. Good luck implementing that algorithm without a general purpose computer.
For instance, the i4i patent is a patent purely on an algorithm, and Microsoft lost that case and had to remove the feature from its software: http://en.swpat.org/wiki/I4i_v._Microsoft . I'm not sure how you can square that with algorithms not being patentable.
It's commonly supposed that the Supreme Court could void these illegal patents - could dissolve this entire illegal industry - with a swish of their shiny polyester robes. Actually they already tried that, in Flook. Jedi mind tricks, which in the end is all the Court really has, worked about as well on Andrew Jackson.
I think this explains the disappointing result of Bilski. If you are supposed to have a magic power which in reality doesn't exist, make every excuse to avoid using it. You may still be suspected of impotence, but at least the suspicion is not confirmed.
Unfortunately there isn't really a solution to the patent problem that's compatible with the rule of law, mostly because the rule of law was so long ago abandoned for the rule of lawyers. Perhaps Andrew Jackson could round them all up and march them to Oklahoma - or at least, Marshall, Texas.
O(k log n log(n/k)) complexity for the general case.
Has anyone else been turned off by the sensationalism of MIT TR articles?
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.
I guess if you use a smaller k it is useful.
However, be wary of algorithms that expect K as input, as they are asking you to classify your signal before analysis.
High-res Dirac video encoding is definitely possible in real-time, you just need a very optimized encoder, which doesn't really exist. Dirac's main speed cost comes from the overlapped-block motion compensation, not the transform.
Implementation of an FFT on a chip has two components: the logic/computing elements ( governed by O(n.log(n)) ) and the routing of signals between those elements. It turns out the size and speed of the FFT is mainly determined by the routing, not by the logic, and there is a tractable routing solution to a reasonable number of points [1]. The computation complexity becomes secondary if the complexity of the implementation is determined by the non-computational aspects.
[1] Based on experience in 1995.
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.
This is a useless post except that I wanted to highlight that wonderful little bon mot. Well done.
- 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
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.
"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.