| 644 | RWTH Publication No: 981229 2024 |
| TITLE | Randomized least-squares with minimal oversampling and interpolation in general spaces |
| AUTHORS | Abdellah Chkifa, Matthieu Dolbeault |
| 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 L2 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. |
| KEYWORDS | Leastsquares, Interpolation, Christoffel function |
