21–30 of 49 posts
Paper at: http://arxiv.org/abs/1201.2501v1 O(k log n log(n/k)) complexity for the general case.
I guess if you use a smaller k it is useful.
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.
This is a useless post except that I wanted to highlight that wonderful little bon mot. Well done.
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.
Disagree. I think that natural scrolling gestures in Mac OS Lion is more revolutionary and more intuitive to use than this "faster Fourier transform". That technology sounds like it only used by nerds, and I'm sure it has a TERRIBLE user experience.
Paper at: http://arxiv.org/abs/1201.2501v1 O(k log n log(n/k)) complexity for the general case.
I thought normally k=n, and the ordinary complexity is O(n log(n)). So this sounds worse for the normal case. 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.
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.
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.
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.
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.
Does this mean real-time Dirac video encoding might be possible?
No, Dirac is based on wavelet transforms, which have different math behind them, not using Fourier transforms. This Sparse Fourier Transform (which the authors are now calling the sFFT) would be more useful for traditional FFT/DCT compression algorithms. Though for the most part, the hardware for even very complicated real-time Fourier-based compression (H.264, HD) already exists.
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.
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…