Randomized least-squares with minimal oversampling and interpolation in general spaces

arXiv (Cornell University)

Abstract

In approximation of functions based on point values, least-squares methods provide more stability than interpolation, at the expense of increasing the sampling budget. We show that near-optimal approximation error can nevertheless be achieved, in an expected $L^2$ sense, as soon as the sample size $m$ is larger than the dimension $n$ of the approximation space by a constant ratio. On the other hand, for $m=n$, we obtain an interpolation strategy with a stability factor of order $n$. The proposed sampling algorithms are greedy procedures based on arXiv:0808.0163 and arXiv:1508.03261, with polynomial computational complexity.

Authors 2

1. Abdellah Chkifa Aachen Institut für Geometrie und Praktische Mathematik [RWTH Aachen]

   RWTH Aachen University · Laboratoire Jacques-Louis Lions

   Affiliation as printed

   Institut für Geometrie und Praktische Mathematik [RWTH Aachen]

   Laboratoire Jacques-Louis Lions

2. Matthieu Dolbeault Aachen

   RWTH Aachen University · Université Mohammed VI Polytechnique

   Affiliation as printed

   RWTH Aachen , Germany

   Université Mohammed VI Polytechnique [Ben Guerir]