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

Author name not available (Why is that?)

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.

Has companion code repository: https://github.com/belloliva/minimal-oversampling-for-multivariate-polynomial-least-squares

Mathematics Subject Classification ID

No records found.

This page was built for publication: Randomized least-squares with minimal oversampling and interpolation in general spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6510543)