Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Given a finite set $ E \subset \mathbb{R}^2 $ with $ \#(E) = N $ and a function $ f : E \to [0,\infty) $, how can we compute the order of magnitude of an optimal (in terms of the $C^2(\mathbb{R}^2)$ norm) nonnegative extension of $ f $? In this talk, I will exhibit an efficient algorithm, that first preprocesses the set $ E $ using $ \mathcal{O}(N\log N) $ operations and $ \mathcal{O}(N) $ storage, and then compute the optimal norm using $ \mathcal{O}(N) $ operations.

We will investigate and improve the so-called ``Finiteness Principle'' for nonnegative interpolation, proven by Fefferman, Israel, and Luli, which reduces an $ N $-dependent large optimization system to a collection of $ N $-independent small subsystems. Then, using tools from combinatorial and computational geometry, we can reduce the number of such systems and identify them efficiently. If time permits, I will talk about the ideas behind the proof of the Finiteness Principle and the notion of ``sparsity" in representing an interpolant.

This is joint work with Kevin Luli.