Functions of Few Coordinate Variables: Sampling Schemes and Recovery Algorithms – Simon Foucart  (Texas A&M University )

June 18, 2019 @ 9:00 am – 9:50 am
Seminar Room 1
Newton Institute

I will revisit in this talk the task of approximating multivariate functions that depend on only a few of their variables. The number of samples required to achieve this task to a given accuracy has been determined for Lipschitz functions several years ago. However, two questions of practical interest remain: can we provide an explicit sampling strategy and can we efficiently produce approximants? I will (attempt to) answer these questions under some additional assumptions on the target function. Firstly, if it is known to be linear, then the problem is exactly similar to the standard compressive sensing problem, and I will review some of recent contributions there. Secondly, if the target function is quadratic, then the problem connects to sparse phaseless recovery and to jointly low-rank and bisparse recovery, for which some results and open questions will be presented. Finally, if the target function is known to increase coordinatewise, then the problem reduces to group testing, from which I will draw the sought-after sampling schemes and recovery algorithms.