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 well-chosen 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 near-linear 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)