Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

Giovanni Migliorati; Fabio Nobile; Erik von Schwerin; Raul Tempone

doi:10.1007/s10208-013-9186-4

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

Giovanni Migliorati, Fabio Nobile, Erik von Schwerin, Raul Tempone

Research output: Contribution to journal › Article › peer-review

63 Scopus citations

Abstract

We analyze the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the polynomial space. Optimality is meant in the sense that the weighted L2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best L∞ error achievable in the given polynomial space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the polynomial degree, and on the smoothness of the target function. © 2014 SFoCM.

Original language	English (US)
Pages (from-to)	419-456
Number of pages	38
Journal	Foundations of Computational Mathematics
Volume	14
Issue number	3
DOIs	https://doi.org/10.1007/s10208-013-9186-4
State	Published - Mar 5 2014

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The authors would like to recognize the support of the PECOS Center at ICES, University of Texas at Austin (Project Number 024550, Center for Predictive Computational Science). Support from the VR project "Effektiva numeriska metoder for stokastiska differentialekvationer med tillampningar" and King Abdullah University of Science and Technology (KAUST) through the AEA projects "Predictability and Uncertainty Quantification for Models of Porous Media" and "Tracking Uncertainties in Computational Modeling of Reactive Systems" is also acknowledged. R. Tempone is a member of the KAUST SRI Center for Uncertainty Quantification. The first and second authors were supported by the Italian Grant FIRB-IDEAS (Project RBID08223Z) "Advanced numerical techniques for uncertainty quantification in engineering and life science problems." We are indebted to A. Cohen and R. DeVore for giving us valuable feedback on the convergence proof. We would also like to thank the anonymous referees for their useful comments that helped us to improve considerably the manuscript, and in particular for the suggestion in the proof of Theorem 2.

ASJC Scopus subject areas

Computational Theory and Mathematics
Computational Mathematics
Theoretical Computer Science
Applied Mathematics
General Mathematics

Access to Document

10.1007/s10208-013-9186-4

Cite this

@article{9ee334cf3c864bdd87e30b5e69a9ba91,

title = "Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations",

abstract = "We analyze the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the polynomial space. Optimality is meant in the sense that the weighted L2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best L∞ error achievable in the given polynomial space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the polynomial degree, and on the smoothness of the target function. {\textcopyright} 2014 SFoCM.",

author = "Giovanni Migliorati and Fabio Nobile and {von Schwerin}, Erik and Raul Tempone",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The authors would like to recognize the support of the PECOS Center at ICES, University of Texas at Austin (Project Number 024550, Center for Predictive Computational Science). Support from the VR project {"}Effektiva numeriska metoder for stokastiska differentialekvationer med tillampningar{"} and King Abdullah University of Science and Technology (KAUST) through the AEA projects {"}Predictability and Uncertainty Quantification for Models of Porous Media{"} and {"}Tracking Uncertainties in Computational Modeling of Reactive Systems{"} is also acknowledged. R. Tempone is a member of the KAUST SRI Center for Uncertainty Quantification. The first and second authors were supported by the Italian Grant FIRB-IDEAS (Project RBID08223Z) {"}Advanced numerical techniques for uncertainty quantification in engineering and life science problems.{"} We are indebted to A. Cohen and R. DeVore for giving us valuable feedback on the convergence proof. We would also like to thank the anonymous referees for their useful comments that helped us to improve considerably the manuscript, and in particular for the suggestion in the proof of Theorem 2.",

year = "2014",

month = mar,

day = "5",

doi = "10.1007/s10208-013-9186-4",

language = "English (US)",

volume = "14",

pages = "419--456",

journal = "Foundations of Computational Mathematics",

issn = "1615-3375",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

AU - Migliorati, Giovanni

AU - Nobile, Fabio

AU - von Schwerin, Erik

AU - Tempone, Raul

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The authors would like to recognize the support of the PECOS Center at ICES, University of Texas at Austin (Project Number 024550, Center for Predictive Computational Science). Support from the VR project "Effektiva numeriska metoder for stokastiska differentialekvationer med tillampningar" and King Abdullah University of Science and Technology (KAUST) through the AEA projects "Predictability and Uncertainty Quantification for Models of Porous Media" and "Tracking Uncertainties in Computational Modeling of Reactive Systems" is also acknowledged. R. Tempone is a member of the KAUST SRI Center for Uncertainty Quantification. The first and second authors were supported by the Italian Grant FIRB-IDEAS (Project RBID08223Z) "Advanced numerical techniques for uncertainty quantification in engineering and life science problems." We are indebted to A. Cohen and R. DeVore for giving us valuable feedback on the convergence proof. We would also like to thank the anonymous referees for their useful comments that helped us to improve considerably the manuscript, and in particular for the suggestion in the proof of Theorem 2.

PY - 2014/3/5

Y1 - 2014/3/5

N2 - We analyze the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the polynomial space. Optimality is meant in the sense that the weighted L2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best L∞ error achievable in the given polynomial space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the polynomial degree, and on the smoothness of the target function. © 2014 SFoCM.

AB - We analyze the problem of approximating a multivariate function by discrete least-squares projection on a polynomial space starting from random, noise-free observations. An area of possible application of such technique is uncertainty quantification for computational models. We prove an optimal convergence estimate, up to a logarithmic factor, in the univariate case, when the observation points are sampled in a bounded domain from a probability density function bounded away from zero and bounded from above, provided the number of samples scales quadratically with the dimension of the polynomial space. Optimality is meant in the sense that the weighted L2 norm of the error committed by the random discrete projection is bounded with high probability from above by the best L∞ error achievable in the given polynomial space, up to logarithmic factors. Several numerical tests are presented in both the univariate and multivariate cases, confirming our theoretical estimates. The numerical tests also clarify how the convergence rate depends on the number of sampling points, on the polynomial degree, and on the smoothness of the target function. © 2014 SFoCM.

UR - http://hdl.handle.net/10754/563433

UR - http://link.springer.com/10.1007/s10208-013-9186-4

UR - http://www.scopus.com/inward/record.url?scp=84900391426&partnerID=8YFLogxK

U2 - 10.1007/s10208-013-9186-4

DO - 10.1007/s10208-013-9186-4

M3 - Article

SN - 1615-3375

VL - 14

SP - 419

EP - 456

JO - Foundations of Computational Mathematics

JF - Foundations of Computational Mathematics

IS - 3

ER -

Analysis of Discrete L2 Projection on Polynomial Spaces with Random Evaluations

Abstract

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this