Source-linked AI summary
Adaptive Leja sparse grid constructions for stochastic collocation and high-dimensional approximation
Akil Narayan, John Jakeman
TL;DR
High-dimensional uncertainty quantification requires selecting parameter samples while model evaluations are costly. The paper develops adaptive sparse grids built from weighted Leja sequences, reporting stronger performance than standard constructions for interpolatory metrics but weaker performance for quadrature metrics.
Problem
Method
The paper uses weighted Leja sequences as nested, granular univariate rules for adaptive Smolyak sparse-grid stochastic collocation.
Source: §4.1 · p. 14, §4.2 · p. 16Results
Leja sparse grids can outperform standard high-order Smolyak constructions in interpolatory metrics but are suboptimal for quadrature metrics.
Source: §6 · p. 20Takeaways & Limitations
Leja rules provide greater adaptive-refinement flexibility than standard composite rules such as Clenshaw-Curtis.
Source: §6 · p. 20Whether weighted Leja sequences have subexponentially growing weighted Lebesgue constants is unknown, and matching Gauss-node distributions does not guarantee good approximation.
Source: (1) (Generalized Hermite) · p. 7
Abstract
from arXiv · showhide
We propose an adaptive sparse grid stochastic collocation approach based upon Leja interpolation sequences for approximation of parameterized functions with high-dimensional parameters. Leja sequences are arbitrarily granular (any number of nodes may be added to a current sequence, producing a new sequence) and thus are a good choice for the univariate composite rule used to construct adaptive sparse grids in high dimensions. When undertaking stochastic collocation one is often interested in constructing weighted approximation where the weights are determined by the probability densities of the random variables. This paper establishes that a certain weighted formulation of one-dimensional Leja sequences produces a sequence of nodes whose empirical distribution converges to the corresponding limiting distribution of the Gauss quadrature nodes associated with the weight function. This property is true even for unbounded domains. We apply the Leja-sparse grid approach to several high-dimensional and problems and demonstrate that Leja sequences are often superior to more standard sparse grid constructions (e.g. Clenshaw-Curtis), at least for interpolatory metrics.
1. Introduction
The introduction motivates sparse-grid stochastic collocation as a way to reduce costly model evaluations in high-dimensional uncertainty quantification. It proposes Leja sequences for their nested, granular refinement and reports weighted-distribution results that connect their nodes to Gauss quadrature nodes, including on unbounded domains.
1. Introduction
- Sparse-grid collocation reduces the number of costly model evaluations by adaptively concentrating evaluations where the approximation is poor.The resulting grid approximates model response to uncertain parameters and can be evaluated inexpensively.Source: §1 · p. 1
- Leja sequences are nested and allow refinement one node at a time, balancing desired grid properties where Gauss-type rules can be weak in monotonicity.The paper identifies efficiency, robustness, monotonicity, and granularity as desirable properties of composite univariate rules.Source: §1 · p. 2
- The paper proposes univariate Leja sequences as composite rules for adaptive sparse-grid approximation, arguing that they compromise between efficiency, granularity, and monotonicity.The first half analyzes one-dimensional weighted Leja sequences; the later sections develop adaptive multivariate grids and evaluate them.Source: §1 · p. 2
- Weighted Leja nodes have the same asymptotic distribution as associated Gauss quadrature nodes for many weights, and contracted sequences are asymptotically weighted Fekete, including on unbounded domains.The distribution result does not itself guarantee good approximation.Source: §1 · p. 2
2. Setup
The setup frames high-dimensional parameter selection as a central bottleneck: tensor products and space-filling designs grow rapidly with dimension. It introduces sparse grids and weighted Leja rules as nested alternatives for high-order approximation, alongside the stochastic model and polynomial-approximation context.
2. Setup
- The setup presents generalized polynomial chaos as a finite-degree polynomial representation of model response, with coefficients determined from sampled model realizations.The coefficients may be found through interpolation, least squares, quadrature, or compressive sampling, depending on sample count and expected accuracy.Source: §2 · p. 3
- At fixed smoothness, functional complexity grows exponentially with parameter dimension, limiting tensor-product and space-filling approaches.Sparse grids use unions of tensorized one-dimensional grids to control mesh cardinality and delay the curse of dimensionality.Source: §2 · p. 3
- Weighted Leja grids are nested and their nodes distribute like one-dimensional Gauss quadrature nodes, combining Gauss-like placement with nested refinement.The setup treats random parameters as deterministic parameters with a corresponding weight function.Source: §2 · pp. 3–4
- Weighted Leja sequences are easy to compute for exotic weight functions, unlike nested Gauss-Kronrod and Gauss-Patterson schemes that are usually restricted to special weights..Source: §2 · p. 4
- The approach considers polynomial approximation on unbounded domains and is most closely related to infinite-domain basis expansions, while truncation and mapping approaches remain possible but outside scope.The paper notes these alternative approaches can perform accurate approximation depending on the application.Source: §2 · p. 4
3. Weighted Leja points
This section develops weighted Leja sequences, describing their asymptotic relationship to Gauss quadrature nodes and their use in interpolation and quadrature. It presents barycentric interpolation formulations and practical considerations, including refinement, error estimation, and the ill-conditioning of interpolation on unbounded domains.
(1) (Generalized Hermite)
- The weighted formulation uses v = √w and can construct sequences on unbounded domains when polynomials are dense in the v-weighted supremum norm.The authors prove the limit result by showing contracted weighted Leja points are asymptotically weighted Fekete; weighted Leja sequences’ subexponential weighted Lebesgue-constant growth remains unknown.Source: §3 · pp. 5–6, (1) (Generalized Hermite) · pp. 7, 9
3.1. Limits of weighted Leja sequences.
- Contracted weighted Leja sequences and the corresponding Gauss nodes converge to the same limiting measure for the classical weight families considered.For unbounded domains with exponential weights, the associated equilibrium weight is the square root of w; for bounded Jacobi-type weights, it is uniform.Source: §3.1 · pp. 6–7, (1) (Generalized Hermite) · p. 7
3.2. Quadrature with Leja sequences.
- Leja interpolatory quadrature rules are relatively well-conditioned for uniform, oscillatory, and Gaussian weights.The reported condition-number analysis also applies to a Gaussian density on R.Source: §3.2 · p. 10, Figure 4 · p. 11
- Leja refinement matches Clenshaw–Curtis in maximum-norm accuracy, performs worse in quadrature accuracy, and permits arbitrary-sized refinements.Gauss–Patterson performs worse in maximum-norm approximation in the reported comparison; its nodes are constructed for polynomial integration rather than interpolation.Source: §3.2 · p. 11, Figure 5 · p. 12
- The Leja hierarchical surplus is a sharper error estimate than the Clenshaw–Curtis surplus and supports refinement at arbitrary sizes.For Clenshaw–Curtis, the surplus at N = 257 does not accurately indicate the error at N = 513 and is conservative; these observations do not hold for Leja.Source: §3.2 · pp. 11–12, Figure 6 · p. 12
3.3. Barycentric Interpolation.
- Barycentric interpolation provides an efficient, numerically robust way to compute and evaluate polynomial interpolants, provided the interpolation problem itself is stable.The passage points to for an introduction to the method.Source: §3.3 · p. 12
- The barycentric formula evaluates the interpolant in O(N) operations after its weights are precomputed, and common rescaling of those weights leaves the interpolant unchanged.When the interpolation operator is well-conditioned, comparable weight magnitudes support a well-conditioned numerical procedure.Source: §3.3 · p. 13
- For Leja sequences, the authors use a v-weighted barycentric formula to interpolate f by interpolating vf with v-weighted polynomials.They use the corresponding v-weighted barycentric weights for nodes generated according to (4).Source: §3.3 · p. 13
- In practice, the chosen normalization gives the v-weighted barycentric weights comparable magnitudes, as expected for a well-conditioned interpolation problem.The reformulation appears numerically well-conditioned but does not avoid troublesome computations; unweighted polynomial interpolation on an unbounded domain remains mathematically ill-conditioned.Source: §3.3 · p. 13
4. Sparse grids with univariate Leja rules
Sparse grids mitigate the cost of high-dimensional approximation by combining selected tensor products of one-dimensional grids. The paper uses nested, arbitrarily refinable Leja sequences and variance-based indicators to guide dimension-adaptive refinement.
4. Sparse grids with univariate Leja rules
- Tensorized sampling grows exponentially with dimension, making full grids generally infeasible for high-dimensional approximation.Sparse grids delay this growth by selecting only certain combinations of tensor products.Source: §4 · pp. 13–14
4.1. Common univariate rules.
- Nested one-dimensional grids form the sparse-grid products, while hierarchical surpluses measure the difference between a new point's function value and the current approximation.The interpolant uses tensor-product Lagrange basis functions associated with grid points.Source: §4.1 · p. 15
- Leja sequences allow sparse-grid refinement to add any number of nodes while keeping coarse grids nested within fine grids.This granularity supports adaptive refinement without requiring a fixed batch of new nodes at each level.Source: §4.1 · pp. 15–16
4.2. Dimension adaptivity.
- Dimension adaptivity selects the active subspace with the largest variance-contribution indicator and refines its admissible forward neighbors.The indicator is calculated by transforming each hierarchical-subspace interpolant into a polynomial chaos expansion; refinement stops at a sample budget or global-indicator threshold.Source: §4.2 · p. 16
5. Numerical examples
Across the examples, Leja sparse grids are usually competitive or superior to standard alternatives for interpolation, but can be weaker for quadrature. The comparisons show that this pattern depends on the model and the refinement structure.
5. Numerical examples
- Leja sparse grids are usually competitive or superior to Clenshaw-Curtis for interpolation, but appear suboptimal when evaluated by quadrature metrics.The authors note that Leja sequences are designed for interpolation, not necessarily quadrature.Source: §5 · p. 16
5.1. Random oscillator.
- Leja nodes yield significantly more accurate oscillator-position interpolants than Clenshaw-Curtis nodes in the six-parameter example.The oscillator is evaluated at T = 20 seconds, and the model is solved analytically to avoid discretization error.Source: Figure 7 · p. 17, §5.1 · p. 17
5.2. Borehole model.
- Leja interpolation is more accurate than Clenshaw-Curtis for a given number of borehole-model evaluations, while Clenshaw-Curtis estimates the mean more accurately.The figure compares mean and RMSE convergence against the number of model evaluations.Source: Figure 8 · p. 18, §5.2 · p. 18
5.3. Heterogeneous diffusion equation.
- For the 40-dimensional diffusion example, Leja is only marginally better than Clenshaw-Curtis for interpolation and exhibits the familiar quadrature difficulty.The authors attribute the limited advantage to ellipsoidal anisotropy: Clenshaw-Curtis refinements in some directions can resolve mixed terms, so Leja granularity is not needed.Source: §5.3 · pp. 18–19, Figure 9 · p. 19
5.4. Resistor network.
- For the 40-dimensional resistor network under Gaussian weights, Leja improves interpolation significantly and produces quadrature results competitive with nested Genz-Keister rules.The Leja sequence is constructed on an infinite domain.Source: §5.4 · p. 19, Figure 11 · p. 20
6. Summary
The paper presents weighted Leja sequences as nested, granular building blocks for adaptive sparse grids and establishes their asymptotic node-distribution relation to Gauss quadrature. Its examples show stronger performance for interpolation than for quadrature metrics.
6. Summary
- Weighted Leja sequences are nested one-dimensional interpolation grids whose empirical node distribution asymptotically coincides with the limiting distribution of corresponding Gauss quadrature nodes.For adaptive multidimensional refinement, Leja grids offer greater dexterity than standard composite rules such as Clenshaw-Curtis.Source: §6 · p. 20
- Across the examples, Leja sparse grids can outperform standard high-order Smolyak constructions for interpolation but are suboptimal for quadrature metrics.The authors identify integral-focused Leja-like rules as future work.Source: §6 · p. 20
7. Proof of Theorem 3.2
The proof establishes weighted Fekete behavior for Leja sequences, then uses weighted potential-theory results to connect it to limiting node distributions. The Jacobi, Hermite, and Laguerre cases require different arguments or conditions.
7.1. Weighted potential theory.
- The proof reduces Theorem 3.1 to Theorem 3.2: show weighted Fekete behavior, then apply the lemma linking such arrays to empirical convergence toward the weighted equilibrium measure.Source: §7.1 · pp. 20–21
7.2. Jacobi case.
- For Jacobi weights with α,β≥0, Leja sequences are ev-asymptotically Fekete; the negative-parameter case shifts the weight and yields an arcsine-limit sequence.The proof treats bounded and unbounded domains with different contraction arguments.Source: §7.2 · pp. 22–23, §7.1 · p. 22
7.3. Hermite case.
- For Hermite weights, the proof defines progressively contracted Leja arrays and targets their ev-weighted asymptotic Fekete property.Source: §7.3 · pp. 23–24
- For Hermite weights with μ>0, weighted Leja points are proved asymptotically weighted Fekete; for μ<0, selecting zero reduces the objective to the μ>0 case.Source: §7.3 · p. 27
7.4. Laguerre case.
- The Laguerre case follows the Hermite argument for weights ev(z)=exp(−|z|) on [0, ∞), using the result with α=1.Source: §7.4 · p. 27