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).