If you have read the latest tech news, the chances are high that you learned about an important discovery in signal processing. Behind it are AUBG graduate Alexander Stoytchev (‘97), who teaches at Iowa State University and his graduate student Vladimir Sukhoy. The two computer engineers discovered an algorithm that has remained a mystery for 50 years. This algorithm, called the inverse chirp z-transform (ICZT) algorithm, will enable the development of new digital applications and the improvement of the performance of the existing ones.
Alexander graduated AUBG with a major in Computer Science and went on to pursue a master’s and a PhD degree in Artificial Intelligence and Robotics from the Georgia Institute of Technology in Atlanta. He was then hired to teach at Iowa State University, where he is now Associate Professor in Electrical and Computer Engineering. “In a way, I have spent the last 25 years at three great universities,” he said.
But joining AUBG back in 1993 was risky, Alexander said. Established in 1991, the university had yet to graduate its first class. In hindsight, he said, “Going to AUBG for my bachelor’s degree was one of the best decisions I’ve ever made. Many of the technical skills that were required for this discovery I learned at AUBG.”
In this interview, Alexander talks about how he first stumbled upon the missing algorithm, how he and Vladimir Sukhoy attacked and solved the problem and what it means for the world of technology.
Could you please explain the meaning and significance of this algorithm? What problems does it solve?
This is a story about four algorithms; three were previously known, one was missing. In 1965, two scientists published the Fast Fourier Transform (FFT) algorithm. That algorithm is very similar to the Inverse Fast Fourier Transform (IFFT) algorithm, which was described at the same time. In 1969, a different group published a generalization of the FFT algorithm, that was called the chirp z-transform (CZT) algorithm. The inverse algorithm for the CZT, however, remained elusive for the next 50 years, until we published it in 2019. Following the convention, we named it the inverse chirp z-transform (ICZT) algorithm.
The FFT and the IFFT are the most important algorithms in Digital Signal Processing (DSP). They are used for processing music, images, and videos. They are also used for wireless communications, such as browsing the Internet over a WiFi network or making a cell phone call using the cellular network. They have multiple other applications in physics, astronomy, electronics, telecommunications, medical imaging, and many other disciplines. They are pervasive in modern devices. In smartphones, for example, they are implemented in hardware using specialized chips that are embedded in the device. These algorithms are directly responsible for the digital revolution. It is not an exaggeration to say that they run a fraction of the world’s economy today.
These algorithms are most useful when they work in pairs. Just like the FFT was matched with the IFFT, it was desirable to match the CZT with a corresponding inverse algorithm. Until we discovered the ICZT algorithm, however, this was not possible. The new algorithm not only generalizes the IFFT algorithm, but also has the same computational complexity, or speed. Because of these properties, it is immediately applicable and could improve the performance of existing applications. It also enables the development of new applications that were not possible before.
How did you first discover the missing algorithm? What inspired you to work on it and how did you solve the puzzle?
Serendipity is the reason for many scientific discoveries, including this one. I was trying to find new and better ways to describe the FFT and the IFFT to the students in my graduate class. I was reading the signal processing textbooks, looking for analogies to describe this pair of algorithms. One of the best analogies is an experiment with light and two triangular prisms that they often do in introductory physics classes. When a beam of white light goes through the first prism it is split into a spectrum of colors. A converging lens and a second prism can then be used to recombine the color spectrum back into white light. In this analogy, the first prism is the FFT, the beam of white light is the input signal (or input vector) to this algorithm, and the color spectrum is the output vector. The second prism is the IFFT, but now the color spectrum is the input vector and the recombined white light is the output vector.
In many of the textbooks I encountered descriptions for a generalization of the FFT, called the CZT algorithm. But the description for the corresponding inverse algorithm was missing in all of them. With the prism analogy in mind, I started to wonder if they had forgotten to describe the second prism (i.e., the inverse algorithm) or if it has not been discovered yet.
I shared this with my graduate student Vladimir Sukhoy and suggested an approach for attacking the problem using structured matrices. We had an initial solution very quickly, but it took a while to fully describe it, test it, and write the research article. We had to perform many computer simulations to evaluate the numerical accuracy of the algorithm and to study its properties. To make things even more interesting, we discovered not one, but two alternative versions of the algorithm. This doubled the amount of work that needed to be done. We even improved the accuracy of the original forward algorithm for a large subset of its parameter space. There were many setbacks, but once we realized what we had discovered there was nothing that could stop us from working on this problem and publishing the solution.
Tell us a bit about your academic and career path: what was your first destination after AUBG and what has happened since then?
I graduated from AUBG in 1997 and won the Best Student in Computer Science award the same year. I also took a lot of math classes, hoping to get a minor, but the math minor was officially approved the semester after I graduated so I never received it on my transcript. But the knowledge and skills that I learned in these math classes have served me well over the years.
I continued my education at the Georgia Institute of Technology, in Atlanta. I earned both my master’s and PhD in Computer Science from Georgia Tech, where I specialized in Artificial Intelligence and Robotics. After graduation, I was hired as an Assistant Professor in Electrical and Computer Engineering at Iowa State University. A couple of years ago I was promoted to Associate Professor with tenure at the same institution. In a way, I have spent the last 25 years at three great universities.
In what ways have your AUBG education, experience, professors and friendships had an impact on your career and who you are today?
Going to AUBG for my bachelor’s degree is one of the best decisions that I’ve ever made.
When I enrolled in 1993, the university had yet to graduate its first class, so it was a risky decision. After I visited the campus, however, I had no doubt that this is where I wanted to go. My classmates were some of the best and brightest students from Bulgaria and the neighboring countries. It was a unique and intellectually stimulating environment. I made a lot of friends and I still keep in touch with many of them.
Many of the technical skills that were required for this discovery I learned at AUBG. For example, our research article that describes the new algorithm combines techniques from Algorithms, Linear Algebra, Discrete Mathematics, and Numerical Analysis. I took classes with these same names while I was a student at AUBG. My former professors deserve a lot of credit for being top-notch teachers.
What advice would you give to recent university graduates about building a fulfilling life and career?
Aim high, do great work!
Photo by Paul Easker, Iowa State University
