Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 


A Christoffel function weighted least squares algorithm for collocation approximations

Authors: Akil Narayan, John D. Jakeman and Tao Zhou
Journal: Math. Comp. 86 (2017), 1913-1947
MSC (2010): Primary 65D15, 41A10
Published electronically: November 28, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Muhammed Ali Alan, Supports of weighted equilibrium measures and examples, Potential Anal. 38 (2013), no. 2, 457-470. MR 3015359,
  • [2] 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,
  • [3] Eric Bedford and B. A. Taylor, The complex equilibrium measure of a symmetric convex set in $ {\bf R}^n$, Trans. Amer. Math. Soc. 294 (1986), no. 2, 705-717. MR 825731,
  • [4] 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.
  • [5] 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,
  • [6] Robert J. Berman, Bergman kernels for weighted polynomials and weighted equilibrium measures of $ \mathbb{C}^n$, Indiana Univ. Math. J. 58 (2009), no. 4, 1921-1946. MR 2542983,
  • [7] Thomas Bloom, Weighted polynomials and weighted pluripotential theory, Trans. Amer. Math. Soc. 361 (2009), no. 4, 2163-2179. MR 2465832,
  • [8] 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,
  • [9] T. Bloom and N. Levenberg, Asymptotics for Christoffel functions of planar measures, J. Anal. Math. 106 (2008), 353-371. MR 2448990,
  • [10] Len Bos, Asymptotics for the Christoffel function for Jacobi like weights on a ball in $ {\bf R}^m$, New Zealand J. Math. 23 (1994), no. 2, 99-109. MR 1313445
  • [11] 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
  • [12] 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,
  • [13] 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,
  • [14] 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,
  • [15] 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,
  • [16] 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,
  • [17] J. Hampton and A. Doostan, Coherence motivated sampling and convergence analysis of least-squares polynomial chaos regression, arXiv: 1410.1931, 2014.
  • [18] M. Klimeck, Pluripotential Theory, Oxford University Press, Oxford, 1991.
  • [19] 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,
  • [20] D. S. Lubinsky, A survey of weighted polynomial approximation with exponential weights, Surv. Approx. Theory 3 (2007), 1-105. MR 2276420
  • [21] 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,
  • [22] 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,
  • [23] 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,
  • [24] 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,
  • [25] Akil Narayan and Tao Zhou, Stochastic collocation on unstructured multivariate meshes, Commun. Comput. Phys. 18 (2015), no. 1, 1-36. MR 3371550,
  • [26] Paul Nevai, Géza Freud, orthogonal polynomials and Christoffel functions. A case study, J. Approx. Theory 48 (1986), no. 1, 167. MR 862231,
  • [27] Holger Rauhut and Rachel Ward, Sparse Legendre expansions via $ \ell _1$-minimization, J. Approx. Theory 164 (2012), no. 5, 517-533. MR 2903116,
  • [28] 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
  • [29] 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.
  • [30] Vilmos Totik, Asymptotics for Christoffel functions for general measures on the real line, J. Anal. Math. 81 (2000), 283-303. MR 1785285,
  • [31] Vilmos Totik, Asymptotics for Christoffel functions with varying weights, Adv. in Appl. Math. 25 (2000), no. 4, 322-351. MR 1788824,
  • [32] Joel A. Tropp, User-friendly tail bounds for sums of random matrices, Found. Comput. Math. 12 (2012), no. 4, 389-434. MR 2946459,
  • [33] Norbert Wiener, The Homogeneous Chaos, Amer. J. Math. 60 (1938), no. 4, 897-936. MR 1507356,
  • [34] Dongbin Xiu, Numerical Methods for Stochastic Computations: A Spectral Method Approach, Princeton University Press, Princeton, NJ, 2010. MR 2723020
  • [35] 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 (electronic). MR 2199923,
  • [36] 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 (electronic). MR 1951058,
  • [37] Yuan Xu, Christoffel functions and Fourier series for multivariate orthogonal polynomials, J. Approx. Theory 82 (1995), no. 2, 205-239. MR 1343834,
  • [38] Yuan Xu, Asymptotics of the Christoffel functions on a simplex in $ {\bf R}^d$, J. Approx. Theory 99 (1999), no. 1, 122-133. MR 1696565,
  • [39] 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,
  • [40] 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.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D15, 41A10

Retrieve articles in all journals with MSC (2010): 65D15, 41A10

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

John D. Jakeman
Affiliation: Computer Science Research Institute, Sandia National Laboratories, 1450 Innovation Parkway, SE, Albuquerque, New Mexico 87123

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

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)
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society