Something is happening on your phone, called Fast Fourier Transform. The so-called FFT is a signal processing algorithm that you use more often than you imagine. It is, according to the title of a research paper, an "algorithm that the whole family can use".
Alexander Stoytchev ̵
It's about streaming music, making a mobile phone call, surfing the web, or taking a selfie.
The FFT algorithm was published in 1965. Four years later, researchers developed a more versatile, generalized version called Chirp Z-Transform (CZT). However, a similar generalization of the inverse FFT algorithm remained unresolved for 50 years.
Until Stoytchev and Vladimir Sukhoy – an Iowa doctoral student focusing on electrical and computer engineering and human-computer interaction – worked together to develop the long-awaited algorithm termed inverse chirp-z transformation (ICZT) Matrix notation – the answer to a 50-year-old puzzle in signal processing. Photo credits: Photo by Paul Easker
As with all algorithms, it is a step-by-step process that solves a problem. In this case, it assigns the output of the CZT algorithm to its input. The two algorithms are similar to a series of two prisms – the first separates the wavelengths of white light into one color spectrum, and the second reverses the process by turning the spectrum back into white light, Stoytchev explained.
Stoytchev and Sukhoy describe their new algorithm in a recent online article by Scientific Reports, a Nature Research Journal. Their work shows that the algorithm corresponds to the computational complexity or speed of its counterpart, that it can be used with exponentially decaying or growing frequency components (as opposed to IFFT) and that it has been tested for numerical accuracy. 19659003] Stoytchev said he came up with the idea of formulating the missing algorithm while looking for analogies to help the PhD students in his course "Computational Perception" understand the fast Fourier transform. He read a lot in the literature on signal processing and could not find anything about the inverse to the associated chirp-Z transformation.
"I became curious," he said. "Is that because they could not explain it, or is it because it does not exist? It turned out to be nonexistent."
And so he decided to find a fast inverse algorithm.  Sukhoy said the inverse algorithm is a more difficult problem than the original forward algorithm, and therefore "we needed better precision and more powerful computers to attack them." He also said that one key is to see the algorithm in the mathematical framework of structured matrices
Even then, there were many computer test runs to show that everything was working – we had to convince ourselves that this was possible. "
It took courage to continue addressing the issue, said James Oliver, director of Iowa State Innovation Student Center and former director of the university's Virtual Reality Applications Center, with Stoytchev and Sukhoy paying tribute to Oliver essay, "that he has created the research environment in which we have been able to do this work for the past three years".
Oliver said Stoytchev deserved his support for a mathematical and computational challenge that had not been resolved 50 years ago: "Alex has always impressed me with his passion and commitment to great research challenges. Research always involves risks and it takes courage to spend years of hard work on a fundamental problem. Alex is a gifted and fearless researcher.
Reference: "Generalization of the Inverse FFT Outside the Unity Circle" by Vladimir Sukhoy and Alexander Stoytchev, October 8, 2019, Scientific Reports .
DOI: 10.1038 / s41598-019-50234-9