Randomized Least-Squares with Minimal Oversampling and Interpolation in General Spaces

SIAM Journal on Numerical Analysis, vol. 62, pp. 1515–1538

Abstract

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 [Formula: see text] sense, as soon as the sample size [Formula: see text] is larger than the dimension [Formula: see text] of the approximation space by a constant multiplicative ratio. On the other hand, for [Formula: see text], we obtain an interpolation strategy with a stability factor of order [Formula: see text]. The proposed sampling algorithms are greedy procedures based on [Batson, Spielman, and Srivastava, Twice-Ramanujan sparsifiers, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, 2009, pp. 255–262] and [Lee and Sun, SIAM J. Comput., 47 (2018), pp. 2315–2336], with polynomial computational complexity.

Authors 2

1. Matthieu Dolbeault Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen, 52062 Germany

2. Abdellah Chkifa

   Université Mohammed VI Polytechnique

   Affiliation as printed

   Mohammed VI Polytechnic University, Ben Guerir 43150, Morocco