Optimization algorithms play a fundamental role in analyzing the vast amount of data available today. Due to the need for fast optimization algorithms, there has been recent interest in understanding the mechanisms which enable optimization algorithms to converge quickly. We gain insight into these algorithms by leveraging techniques from control theory. This allows us to not only analyze existing algorithms, but also design new ones.
In this talk, I both design and analyze a novel gradient-based algorithm for unconstrained convex optimization. When the objective function is smooth and strongly convex, the iterates converge linearly to the optimizer with the fastest known guaranteed rate. For high desired accuracies the corresponding iteration complexity is within a factor of two of Nesterov’s theoretical lower bound. I will give a simple convergence proof in the time domain using convex interpolation, and then provide intuition into the design of the method using integral quadratic constraints in the frequency domain. The new algorithm, called the triple momentum method, can be seen as an extension of methods such as gradient descent, Nesterov’s accelerated gradient descent, and the heavy-ball method.
&
The Discrete Fourier Transform is one of the most popular applied transforms. This is due to its pivotal role in signal processing/data analysis and efficient implementation on a computer using the famous fast Fourier transform (FFT). However in the new state of the art of wireless signal processing many digital signals may have extremely high dimension N>10^6, but with only few non-zero coordinates, i.e. sparse, in Fourier domain. In some such cases one can significantly outperform FFT using the sparse FFT (sFFT) method. In the first part of the talk I will describe the building blocks of most modern sFFT algorithms. I will then describe an application of sFFT to wireless channel estimation, that comes from a structure closely related to the Heisenberg Canonical Commutation Relations (CCR).
Discovery Building, Orchard View Room
Alisha Zachariah, Bryan Van Scoy