A Christoffel function weighted least squares algorithm for collocation approximations

Narayan, Akil; Jakeman, John; Zhou, Tao

doi:10.1090/mcom/3192

A Christoffel function weighted least squares algorithm for collocation approximations
HTML articles powered by AMS MathViewer

by Akil Narayan, John D. Jakeman and Tao Zhou;

Math. Comp. 86 (2017), 1913-1947

DOI: https://doi.org/10.1090/mcom/3192

Published electronically: November 28, 2016

PDF | Request permission

Abstract:

We propose, theoretically investigate, and numerically validate an algorithm for the Monte Carlo solution of least-squares polynomial approximation problems in a collocation framework. Our investigation is motivated by applications in the collocation approximation of parametric functions, which frequently entails construction of surrogates via orthogonal polynomials. A standard Monte Carlo approach would draw samples according to the density defining the orthogonal polynomial family. Our proposed algorithm instead samples with respect to the (weighted) pluripotential equilibrium measure of the domain, and subsequently solves a weighted least-squares problem, with weights given by evaluations of the Christoffel function. We present theoretical analysis to motivate the algorithm, and numerical results that show our method is superior to standard Monte Carlo methods in many situations of interest.

References

Muhammed Ali Alan, Supports of weighted equilibrium measures and examples, Potential Anal. 38 (2013), no. 2, 457–470. MR 3015359, DOI 10.1007/s11118-012-9281-1
Volker Barthelmann, Erich Novak, and Klaus Ritter, High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12 (2000), no. 4, 273–288. Multivariate polynomial interpolation. MR 1768951, DOI 10.1023/A:1018977404843
Eric Bedford and B. A. Taylor, The complex equilibrium measure of a symmetric convex set in $\textbf {R}^n$, Trans. Amer. Math. Soc. 294 (1986), no. 2, 705–717. MR 825731, DOI 10.1090/S0002-9947-1986-0825731-8
R. Berman, S. Boucksom, and D. Nyström, Fekete points and convergence towards equilibrium measures on complex manifolds, Acta Mathematica 207 (2011), no. 1, 1–27.
Robert J. Berman, Bergman kernels and equilibrium measures for line bundles over projective manifolds, Amer. J. Math. 131 (2009), no. 5, 1485–1524. MR 2559862, DOI 10.1353/ajm.0.0077
Robert J. Berman, Bergman kernels for weighted polynomials and weighted equilibrium measures of $\Bbb C^n$, Indiana Univ. Math. J. 58 (2009), no. 4, 1921–1946. MR 2542983, DOI 10.1512/iumj.2009.58.3644
Thomas Bloom, Weighted polynomials and weighted pluripotential theory, Trans. Amer. Math. Soc. 361 (2009), no. 4, 2163–2179. MR 2465832, DOI 10.1090/S0002-9947-08-04607-2
T. Bloom, L. Bos, N. Levenberg, and S. Waldron, On the convergence of optimal measures, Constr. Approx. 32 (2010), no. 1, 159–179. MR 2659752, DOI 10.1007/s00365-009-9078-7
T. Bloom and N. Levenberg, Asymptotics for Christoffel functions of planar measures, J. Anal. Math. 106 (2008), 353–371. MR 2448990, DOI 10.1007/s11854-008-0052-2
Len Bos, Asymptotics for the Christoffel function for Jacobi like weights on a ball in $\textbf {R}^m$, New Zealand J. Math. 23 (1994), no. 2, 99–109. MR 1313445
L. Bos, B. Della Vecchia, and G. Mastroianni, On the asymptotics of Christoffel functions for centrally symmetric weight functions on the ball in $\mathbf R^d$, Proceedings of the Third International Conference on Functional Analysis and Approximation Theory, Vol. I (Acquafredda di Maratea, 1996), 1998, pp. 277–290. MR 1644555
D. Burns, N. Levenberg, S. Ma’u, and Sz. Révész, Monge-Ampère measures for convex bodies and Bernstein-Markov type inequalities, Trans. Amer. Math. Soc. 362 (2010), no. 12, 6325–6340. MR 2678976, DOI 10.1090/S0002-9947-2010-04892-5
Abdellah Chkifa, Albert Cohen, Giovanni Migliorati, Fabio Nobile, and Raul Tempone, Discrete least squares polynomial approximation with random evaluations—application to parametric and stochastic elliptic PDEs, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 3, 815–837. MR 3342229, DOI 10.1051/m2an/2014050
Albert Cohen, Mark A. Davenport, and Dany Leviatan, On the stability and accuracy of least squares approximations, Found. Comput. Math. 13 (2013), no. 5, 819–834. MR 3105946, DOI 10.1007/s10208-013-9142-3
Alireza Doostan and Houman Owhadi, A non-adapted sparse approximation of PDEs with stochastic inputs, J. Comput. Phys. 230 (2011), no. 8, 3015–3034. MR 2774328, DOI 10.1016/j.jcp.2011.01.002
Oliver G. Ernst, Antje Mugler, Hans-Jörg Starkloff, and Elisabeth Ullmann, On the convergence of generalized polynomial chaos expansions, ESAIM Math. Model. Numer. Anal. 46 (2012), no. 2, 317–339. MR 2855645, DOI 10.1051/m2an/2011045
J. Hampton and A. Doostan, Coherence motivated sampling and convergence analysis of least-squares polynomial chaos regression, arXiv: 1410.1931, 2014.
M. Klimeck, Pluripotential Theory, Oxford University Press, Oxford, 1991.
A. Kroó and D. S. Lubinsky, Christoffel functions and universality in the bulk for multivariate orthogonal polynomials, Canad. J. Math. 65 (2013), no. 3, 600–620. MR 3043043, DOI 10.4153/CJM-2012-016-x
D. S. Lubinsky, A survey of weighted polynomial approximation with exponential weights, Surv. Approx. Theory 3 (2007), 1–105. MR 2276420
Giovanni Migliorati, Multivariate Markov-type and Nikolskii-type inequalities for polynomials associated with downward closed multi-index sets, J. Approx. Theory 189 (2015), 137–159. MR 3280676, DOI 10.1016/j.jat.2014.10.010
G. Migliorati, F. Nobile, E. von Schwerin, and R. Tempone, Analysis of discrete $L^2$ projection on polynomial spaces with random evaluations, Found. Comput. Math. 14 (2014), no. 3, 419–456. MR 3201952, DOI 10.1007/s10208-013-9186-4
G. Migliorati, F. Nobile, E. von Schwerin, and R. Tempone, Approximation of quantities of interest in stochastic PDEs by the random discrete $L^2$ projection on polynomial spaces, SIAM J. Sci. Comput. 35 (2013), no. 3, A1440–A1460. MR 3061475, DOI 10.1137/120897109
Akil Narayan and Dongbin Xiu, Stochastic collocation methods on unstructured grids in high dimensions via interpolation, SIAM J. Sci. Comput. 34 (2012), no. 3, A1729–A1752. MR 2970271, DOI 10.1137/110854059
Akil Narayan and Tao Zhou, Stochastic collocation on unstructured multivariate meshes, Commun. Comput. Phys. 18 (2015), no. 1, 1–36. MR 3371550, DOI 10.4208/cicp.020215.070515a
Paul Nevai, Géza Freud, orthogonal polynomials and Christoffel functions. A case study, J. Approx. Theory 48 (1986), no. 1, 3–167. MR 862231, DOI 10.1016/0021-9045(86)90016-X
Holger Rauhut and Rachel Ward, Sparse Legendre expansions via $\ell _1$-minimization, J. Approx. Theory 164 (2012), no. 5, 517–533. MR 2903116, DOI 10.1016/j.jat.2012.01.008
Edward B. Saff and Vilmos Totik, Logarithmic potentials with external fields, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 316, Springer-Verlag, Berlin, 1997. Appendix B by Thomas Bloom. MR 1485778, DOI 10.1007/978-3-662-03329-6
T. Tang and T. Zhou, On discrete least-squares projection in unbounded domain with random evaluations and its application to parametric uncertainty quantification, SIAM Journal on Scientific Computing (2014), A2272–A2295.
Vilmos Totik, Asymptotics for Christoffel functions for general measures on the real line, J. Anal. Math. 81 (2000), 283–303. MR 1785285, DOI 10.1007/BF02788993
Vilmos Totik, Asymptotics for Christoffel functions with varying weights, Adv. in Appl. Math. 25 (2000), no. 4, 322–351. MR 1788824, DOI 10.1006/aama.2000.0698
Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389–434. MR 2946459, DOI 10.1007/s10208-011-9099-z
Norbert Wiener, The Homogeneous Chaos, Amer. J. Math. 60 (1938), no. 4, 897–936. MR 1507356, DOI 10.2307/2371268
Dongbin Xiu, Numerical methods for stochastic computations, Princeton University Press, Princeton, NJ, 2010. A spectral method approach. MR 2723020
Dongbin Xiu and Jan S. Hesthaven, High-order collocation methods for differential equations with random inputs, SIAM J. Sci. Comput. 27 (2005), no. 3, 1118–1139. MR 2199923, DOI 10.1137/040615201
Dongbin Xiu and George Em Karniadakis, The Wiener-Askey polynomial chaos for stochastic differential equations, SIAM J. Sci. Comput. 24 (2002), no. 2, 619–644. MR 1951058, DOI 10.1137/S1064827501387826
Yuan Xu, Christoffel functions and Fourier series for multivariate orthogonal polynomials, J. Approx. Theory 82 (1995), no. 2, 205–239. MR 1343834, DOI 10.1006/jath.1995.1075
Yuan Xu, Asymptotics of the Christoffel functions on a simplex in $\textbf {R}^d$, J. Approx. Theory 99 (1999), no. 1, 122–133. MR 1696565, DOI 10.1006/jath.1998.3312
Tao Zhou, Akil Narayan, and Dongbin Xiu, Weighted discrete least-squares polynomial approximation using randomized quadratures, J. Comput. Phys. 298 (2015), 787–800. MR 3374578, DOI 10.1016/j.jcp.2015.06.042
T. Zhou, A. Narayan, and Z. Xu, Multivariate discrete least-squares approximations with a new type of collocation grid, SIAM Journal on Scientific Computing (2014), A2401–A2422.