Posts Tagged ‘FFT’

I came across a really neat web demo of a mathematics equation hand-writing recognition tool called Web Equation. It can be used to recognize a hand-written mathematical expression (using your computer mouse or track-pad), and then convert it to the corresponding LaTeX or MathML code fragment. A few moments after the user has ‘drawn’ the formula, the code-fragment appears in a small box and can then be copy-and-pasted into your document editor.

When creating technical documents using the LaTeX document markup language, mathematical equations can get complicated enough to require frequent visits to the corresponding reference manuals. This tool is apparently written using JavaScript and simplifies the process of creating equations through an intuitive interface and a simple cut-and-paste operation.

It does pretty well with my track-pad written Discrete Fourier Transform:

Read Full Post »

An even faster Fourier transform

A group of MIT researchers have found a way to speed-up the fast Fourier transform for certain types of input data. The technique is described in an unpublished paper, which can be downloaded at this link.

From their abstract:

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show:
• An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and
• An O(k log n log(n/k))-time algorithm for general input signals.
Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). Further, they are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = nΩ(1).
We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Ω(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.

Read Full Post »