Approximation Theory & Convex Optimization

The main goal is to integrate modern optimization techniques (and in particular the Moment-SOS hierarchy) into classical topics in Approximation Theory to advance the state-of-the-art. For instance in the pioneering work "S. Foucart. Computation of Minimal Projections and Extensions, Num. Funct. Anal. Optim., vol 37 (2016)", the determination of minimal projections is examined from an optimization theory viewpoint. It is shown how to transform the problem into appropriate linear programs and obtain approximations that are significantly better than those obtained with more traditional approaches. More recently the same problem has been attacked with the moment-SOS hierarchy to again otain even better approximations. This research program is conducted in collaboration with Simon Foucart (Math. Department, Texas A&M University).

 

Still in this spirit we have also explored the use of the Christoffel-Darboux (CD) kernel to recover solutions of problems in various applications of the Moment-SOS hierarchy. In this methodology,  an optimal solution of some Semidefinite relaxation in the hierarchy provides not the solution itself, but rather an approximation of moments of a measure supported on the solution. So in a final step one has to recover the solution from knowldege of finitely many moments of this measure. This approach covers applications in many areas from standard global optimizatio, to computational geometry, signal processing, probability statistics, control, optimal control and non-linear PDEs. For example, in the latter applications in PDEs, we obtain moments of the measure dµ(x,y)  supported on the graph {(x,f(x)): x in X} of the solution x→f(x). The novelty of the approach is to compute the degree-n CD-Kernel K_n(x,y) associated with µ, and given an arbitrary "x in X", solve f(x):= y^*=argmin_y K_n(x,y).  In doing so and in contrast to many other standard approaches, one does not approximate the (possibly discontinuous) solution f by a polynomial but rather by a semi-algebraic function (the argmin of a polynomial) which permits to avoid a typical Gibbs  phenomenon. See for instance

 

We have also extended this approximation technique to the case of incomplete moment information on µ. The idea is to approximate the missing information by solving a hierarchy of semidefinite programs (performing a moment  matrix completion) via minimizing an appropriate sparsity-inducing criterion. We claim that this approach is an infinite-dimensional analogue of Super-Resolution by Candès and Fernandez-Granda for atomic univariate signals. See