Paper Info
Title
Analysis of discrete least squares on multivariate polynomial spaces with evaluations at low-discrepancy point sets
Abstract
We analyze the stability and accuracy of discrete least squares on multivariate polynomial 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 Cohen et¿al. (2013), Migliorati et¿al. (2014), Migliorati (2013) and Chkifa et¿al. (in press) 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.
Year
DOI
Venue
2015
10.1016/j.jco.2015.02.001
Journal of Complexity
Keywords
Field
DocType
Approximation theory,Discrete least squares,Error analysis,Multivariate polynomial approximation,Low-discrepancy point set,Nonparametric regression
Alternating polynomial,Discrete mathematics,Stable polynomial,Polynomial,Mathematical analysis,Monic polynomial,Reciprocal polynomial,Homogeneous polynomial,Wilkinson's polynomial,Matrix polynomial,Mathematics
Journal
Volume
Issue
ISSN
31
4
0885-064X
Citations 
PageRank 
References 
5
0.54
16
Authors
2
Name
Order
Citations
PageRank
Giovanni Migliorati1101.41
Fabio Nobile233629.63