Algorithm Innovation Solves 50-year Puzzle in Signal Processing

Something called the fast Fourier transform
is running on your cell phone right now. The FFT, as it is known, is a
signal-processing algorithm that you use more than you realize.

Alexander Stoytchev – an associate
professor of electrical and computer engineering at Iowa State University - says the FFT algorithm and its inverse (known as the IFFT) are at the
heart of signal processing. And, as such, “These are algorithms that
made the digital revolution possible,” he said. They’re a part of streaming music, making a
cell phone call, browsing the internet or taking a selfie.

The FFT algorithm was published in 1965.
Four years later, researchers developed a more versatile, generalized version
called the chirp z-transform (CZT). But a similar generalization of the inverse
FFT algorithm has gone unsolved for 50 years.

Until, that is, Stoytchev and Vladimir
Sukhoy – an Iowa State doctoral student co-majoring in electrical and computer
engineering, and human computer interaction – worked together to come up with
the long-sought algorithm, called the inverse chirp z-transform (ICZT).

Like all algorithms, it’s a step-by-step
process that solves a problem. In this case, it maps the output of the CZT
algorithm back to its input. The two algorithms are a little like a series of
two prisms – the first separates the wavelengths of white light into a spectrum
of colors and the second reverses the process by combining the spectrum back
into white light, Stoytchev explained.

Stoytchev and Sukhoy describe their new
algorithm in a paper, which shows that the algorithm matches the
computational complexity or speed of its counterpart, that it can be used with
exponentially decaying or growing frequency components (unlike the IFFT) and
that it has been tested for numerical accuracy.

Stoytchev said he stumbled on the idea to
attempt to formulate the missing algorithm while looking for analogies to help
the graduate students in his “Computational Perception” course understand the
fast Fourier transform. He read a lot of the signal-processing literature and
couldn’t find anything about the inverse to the related chirp z-transform.

“I got curious,” he said. “Is that because
they couldn’t explain it, or is it because it doesn’t exist? It turned out it
didn’t exist.” And so he decided to try to find a fast
inverse algorithm.

Sukhoy said the inverse algorithm is a
harder problem than the original, forward algorithm and so “we needed better
precision and more powerful computers to attack it.” He also said a key was
seeing the algorithm within the mathematical framework of structured matrices.

Even then, there were lots of computer test
runs “to show everything was working – we had to convince ourselves that this
could be done.”

Reference

Sukhoy and Stoytchev (2019). Generalizing
the inverse FFT off the unit circle. Scientific Reports. DOI: https://doi.org/10.1038/s41598-019-50234-9

This article has been republished from the
following materials. Note: material may have been edited for length and
content. For further information, please contact the cited source.