## 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 PDF
- Math. Comp.
**86**(2017), 1913-1947 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.

## Additional Information

**Akil Narayan**- Affiliation: Department of Mathematics and Scientific Computing and Imaging (SCI) Institute, University of Utah, University of Utah, Salt Lake City, Utah 84112
- MR Author ID: 932761
- Email: akil@sci.utah.edu
**John D. Jakeman**- Affiliation: Computer Science Research Institute, Sandia National Laboratories, 1450 Innovation Parkway, SE, Albuquerque, New Mexico 87123
- MR Author ID: 862962
- Email: jdjakem@sandia.gov
**Tao Zhou**- Affiliation: LSEC, Institute of Computational Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, People’s Republic of China
- MR Author ID: 908982
- Email: tzhou@lsec.cc.ac.cn
- Received by editor(s): December 14, 2014
- Received by editor(s) in revised form: June 8, 2015, September 19, 2015, and January 29, 2016
- Published electronically: November 28, 2016
- Additional Notes: The first author was partially supported by AFOSR FA9550-15-1-0467 and DARPA N660011524053

The third author was supported the National Natural Science Foundation of China (Award Nos. 91530118 and 11571351) - © Copyright 2016 American Mathematical Society
- Journal: Math. Comp.
**86**(2017), 1913-1947 - MSC (2010): Primary 65D15, 41A10
- DOI: https://doi.org/10.1090/mcom/3192
- MathSciNet review: 3626543