MATHICSE Technical Report : Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets

We analyze the stability and accuracy of discrete least squares on multivariate poly- nomial spaces to approximate a given function depending on a multivariate random variable uniformly distributed on a hypercube. The polynomial approximation is calculated starting from pointwise noise-free evaluations of the target function at low- discrepancy point sets. We prove that the discrete least-squares approximation, in a multivariate anisotropic tensor product polynomial space and with evaluations at low-discrepancy point sets, is stable and accurate under the condition that the number of evaluations is proportional to the square of the dimension of the polynomial space, up to logarithmic factors. This result is analogous to those obtained in [7, 22, 19, 6] for discrete least squares with random point sets, however it holds with certainty instead of just with high probability. The result is further generalized to arbitrary polynomial spaces associated with downward closed multi-index sets, but with a more demanding (and probably nonoptimal) proportionality between the number of evaluation points and the dimension of the polynomial space.