Randomized least-squares with minimal oversampling and interpolation in general spaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910328092098560 |
|---|---|
| author | Chkifa, Abdellah Dolbeault, Matthieu |
| author_facet | Chkifa, Abdellah Dolbeault, Matthieu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_07435 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Randomized least-squares with minimal oversampling and interpolation in general spaces Chkifa, Abdellah Dolbeault, Matthieu Numerical Analysis 65D15, 41A65, 65D05, 41A81, 41A05 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. |
| title | Randomized least-squares with minimal oversampling and interpolation in general spaces |
| topic | Numerical Analysis 65D15, 41A65, 65D05, 41A81, 41A05 |
| url | https://arxiv.org/abs/2306.07435 |