Sequential sampling for optimal weighted least squares approximations in hierarchical spaces

17 pages, 7 figuresWe consider the problem of approximating an unknown function $u\in L^2(D,\rho)$from its evaluations at given sampling points $x^1,\dots,x^n\in D$, where $D\subset \mathbb{R}^d$ is a generaldomain and $\rho$ a probability measure. The approximation is picked in alinear space $V_m$ where $m=\dim(V_m)$ and computed by a weighted least squares method. Recentresults show the advantages of picking the sampling points at randomaccording to a well-chosen probability measure $\mu$ that depends both on $V_m$ and $\rho$.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 $L^2(D,\rho)$-orthonormal projection onto $V_m$,in a near-linear sampling regime $n\sim{m\log m}$. The present paper is motivatedby the adaptive approximation context, in which one typically generates a nested sequence of spaces $(V_m)_{m\geq1}$ with increasing dimension. Although the measure $\mu=\mu_m$ changes with $V_m$, it is possible to recyclethe previously generated samples by interpreting $\mu_m$ as a mixturebetween $\mu_{m-1}$ and an update measure $\sigma_m$. Based on this observation,we discuss sequential sampling algorithms that maintain the stabilityand approximation properties uniformly over all spaces $V_m$. Our main resultis that the total number of computed sample at step $m$ remains of the order $m\log{m}$with high probability. Numerical experiments confirm this analysis