Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. In practice, we are often interested in signals with ``simple'' Fourier structure -- e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies. More broadly, any prior knowledge about a signal's Fourier power spectrum can constrain its complexity.  Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct.

We formalize this intuition by showing that, roughly speaking, a continuous signal from a given class can be approximately reconstructed using a number of samples equal to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction.

Surprisingly, we also show that, up to logarithmic factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present a simple, efficient, and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art. At the same time, it gives the first computationally and sample efficient solution to a broad range of problems, including multiband signal reconstruction and common kriging and Gaussian process regression tasks.

Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal fitting problem. We believe that these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.

This is joint work with Michael Kapralov, Cameron Musco, Christopher Musco, Ameya Velingker and Amir Zandieh

A link for this talk will be sent to our mailing list a day or two in advance.  If you are not on the list and wish to be sent a link, please send email to trefethen@maths.ox.ac.uk.

Kirigami, the relatively unheralded cousin of origami, is the art of cutting paper to articulate and deploy it as a whole. By varying the number, size, orientation and coordination of the cuts, artists have used their imagination and intuition to create remarkable sculptures in 2 and 3 dimensions. I will describe some of our attempts to quantify the inverse problem that artists routinely solve, combining elementary mathematical ideas, with computations and physical models. 

TBA

One of the key objects in studying the Hilbert Scheme of points in the plane is a torus action of $(\mathbb{C}^*)^2$. The fixed points of this action correspond to monomial ideals in $\mathbb{C}[x,y]$, and this gives a connection between the geometry of Hilbert schemes and partition combinatorics. Using this connection, one can extract identities in partition combinatorics from algebro-geometric information and vice versa. I will give some examples of combinatorial identities where as yet the only proofs we have rely on the geometry of Hilbert schemes. If there is time, I will also sketch out a hope that such identities can also be seen by representations of appropriately chosen algebras.