View abstract

Session III.5 - Information-Based Complexity

Monday, June 19, 16:30 ~ 17:00

Weighted least-squares approximation in expected $L^2$ norm

Matthieu Dolbeault

Sorbonne Université, France   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

We investigate the problem of approximating a function $u$ in $L^2$ with a linear space of functions of dimension $n$, using only evaluations of $u$ at $m$ chosen points. A first approach, based on weighted least-squares at i.i.d random points, provides a near-best approximation of $u$, but requires $m$ of order $n \log(n)$. A reduction to a linear sample size, while preserving the quality of approximation can be obtained based on the solution to the Kadison-Singer problem. We improve on this result by using a randomized greedy strategy, which allows to reduce the oversampling ratio $m/n$ and provides an algorithm of polynomial complexity.

Joint work with Albert Cohen (Sorbonne Université, France) and Abdellah Chkifa (Mohammed VI Polytechnic University, Morocco).

View abstract PDF