Overview

Mini-course on Sublinear-Time Algorithms for Approximating Functions of Many Variables

May 16-18, 2022

Laboratory : Applied Mathematics

The course will be delivered in hybrid format: In person (with limited seats) and via Zoom (the link will be provided after registration).

DESCRIPTION:  Compressive sensing has generated tremendous amounts of interest since first being proposed by Emmanuel Candes, David Donoho, Terry Tao, and others a bit more than a decade ago.  This mathematical framework has its origins in (i) the observation that traditional signal processing applications, such as MRI imaging problems, often deal with the acquisition of signals which are known a priori to be sparse in some basis, as well as (ii) the subsequent realization that this knowledge could in fact be used to help streamline the signal acquisition process in the first place (by taking the bare minimum of signal measurements necessary in order to discover and then reconstruct the important basis coefficients only).  The resulting mathematical theory has since led to dramatic reductions in measurement needs over traditional approaches in many situations where one would previously have reconstructed a fuller set of a given signal's basis coefficients only to later discard most of them as insignificant.

Though extremely successful at reducing the number of measurements needed in order to reconstruct a given signal, most standard compressive sensing recovery algorithms still individually represent every basis function during the signal's numerical reconstruction.  This leads one to ask a computationally oriented variant of the original question which led to the development of compressive sensing in the first place:  why should one consider all possible basis coefficients individually during the numerical reconstruction of a given signal when one knows in advance that only a few of them will end up being significant?  In fact, it turns out that one often does not have to explicitly consider each basis function individually during the reconstruction process, and so can reduce both the measurement needs *and* computational complexity of signal reconstruction to depend on the bare minimum of signal measurements necessary in order to reconstruct the important basis coefficients in many settings.  This series of lectures will discuss a class of sublinear-time numerical methods which do exactly this for functions that are sparse in the one-dimensional Fourier basis, as well as the extension of such techniques to produce new fast methods for approximating functions of many variables with respect to the multi-variate Fourier basis.  The course will then conclude with the further extension of similar techniques to tackle multivariate functions which exhibit approximate sparsity in other (non-Fourier) orthonormal polynomial bases.

SUGGESTED PREREQUISITES: The class will be taught at an introductory graduate student level appropriate for beginning PhD students and beyond.  The following background would be most helpful: 

• A strong background in (numerical) linear algebra

•A working familiarity with Fourier series, trigonometric polynomials, and basic Hilbert space ideas

•Knowledge of undergraduate-level number theory and finite fields (e.g., the Chinese remainder theorem, polynomials over finite fields, etc.)

REGISTRATION IS FREE BUT MANDATORY