Matthieu Dolbeault

We investigate the problem of approximating a function in L^2 based on evaluations of the function at some chosen points. A first approach, using weighted least-squares at i.i.d random points, provides a near-best approximation, but with a sampling budget larger (by a logarithmic factor) than the dimension of the approximation space. To reduce the gap between these two quantities, we need non i.i.d methods relying on linear algebra for sums of rank-one matrices.