SILO



The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group

3M

with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Analysis and Design of First-Order Methods for Smooth Strongly Convex Optimization & Low-Complexity Channel Estimation via the Sparse Fast Fourier Transform

Bryan Van Scoy & Alisha Zachariah,

Date and Time: Nov 01, 2017 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building

Abstract:

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).

https://vimeo.com/241745554