596

RWTH Publication No: 960328 2018 
TITLE 
Sequential sampling for optimal weighted least squares approximations in hierarchical spaces 
AUTHORS 
Benjamin Arras, Markus Bachmayr, Albert Cohen 
ABSTRACT 
We consider the problem of approximating an unknown function u∈L2(D,ρ) from its evaluations at given sampling points x1,…,xn∈D, where D⊂Rd is a general domain and ρ is a probability measure. The approximation is picked in a linear space Vm where m=dim(Vm) and computed by a weighted least squares method. Recent results show the advantages of picking the sampling points at random according to a wellchosen probability measure μ that depends both on Vm and ρ. With such a random design, the weighted least squares approximation is proved to be stable with high probability, and having precision comparable to that of the exact L2(D,ρ)orthonormal projection onto Vm, in a nearlinear sampling regime n∼mlogm. The present paper is motivated by the adaptive approximation context, in which one typically generates a nested sequence of spaces (Vm)m≥1 with increasing dimension. Although the measure μ=μm changes with Vm, it is possible to recycle the previously generated samples by interpreting μm as a mixture between μm−1 and an update measure σm. Based on this observation, we discuss sequential sampling algorithms that maintain the stability and approximation properties uniformly over all spaces Vm. Our main result is that the total number of computed sample at step m remains of the order mlogm with high probability. Numerical experiments confirm this analysis. 
KEYWORDS 
weighted least squares, random matrices, optimal sampling measures, hierarchical approximation spaces, sequential sampling 
DOI 
10.1137/18M1189749 
PUBLICATION 
SIAM Journal on Mathematics of Data ScienceVol. 1, Iss. 1 (2019) 