Source-linked AI summary
Enhancing $\ell_1$-minimization estimates of polynomial chaos expansions using basis selection
John D. Jakeman, Michael S. Eldred, Khachik Sargsyan
TL;DR
The paper addresses how fixed PCE truncations can hinder ℓ1-based coefficient recovery, especially as basis size grows or important interactions are omitted. It introduces adaptive basis selection that targets large coefficients and reports more accurate PCEs for a given computational budget, including with gradients and non-uniform inputs. The method's performance is constrained by conditioning issues for Hermite-based systems as sample counts increase.
Problem
Fixed PCE truncations can grow rapidly with dimension or omit important interaction terms, limiting accurate ℓ1-minimization-based coefficient recovery.
Method
The paper adaptively selects PCE basis terms believed to have large coefficients, producing anisotropic bases while limiting unimportant terms that increase mutual coherence.
Results
Basis selection produces more accurate PCEs than fixed a priori bases for a given computational budget and supports high-order terms, gradients, and non-uniform random variables.
Takeaways & Limitations
Adaptive truncation can improve PCE accuracy across high- and lower-dimensional settings while leveraging gradient information and non-uniform random variables.
Takeaways & Limitations
Hermite-polynomial linear systems can suffer poor conditioning as the number of samples increases, and sampling or pre-conditioning strategies for normal variables remain future work.
Abstract
from arXiv · showhide
In this paper we present a basis selection method that can be used with $\ell_1$-minimization to adaptively determine the large coefficients of polynomial chaos expansions (PCE). The adaptive construction produces anisotropic basis sets that have more terms in important dimensions and limits the number of unimportant terms that increase mutual coherence and thus degrade the performance of $\ell_1$-minimization. The important features and the accuracy of basis selection are demonstrated with a number of numerical examples. Specifically, we show that for a given computational budget, basis selection produces a more accurate PCE than would be obtained if the basis is fixed a priori. We also demonstrate that basis selection can be applied with non-uniform random variables and can leverage gradient information.
1. Introduction
The paper targets parametric uncertainty quantification with PCE and ℓ1-minimization, focusing on how basis truncation affects coefficient recovery. It introduces adaptive basis selection to improve accuracy under fixed computational budgets and across several problem settings.
- Motivation: PCEs provide surrogate models for propagating input uncertainty and estimating output statistics without further expensive model evaluations.The paper focuses on stochastic collocation and PCEs as nonintrusive approximations for computational models.
- Motivation: ℓ1-minimization can estimate PCE coefficients from small, possibly arbitrarily positioned collocation sets when the expansion is sparse or compressible.Recovery depends on coefficient decay, collocation samples, and the chosen truncation.
- Research gap: Total-degree bases grow factorially with dimension, while hyperbolic truncations can omit important interaction terms and perform poorly when those terms have large coefficients.These limitations motivate adapting the basis to the function being approximated.
- Contribution: The proposed algorithm iteratively selects PCE basis terms so ℓ1-minimization focuses on terms expected to have large coefficients.The method is designed to replace a priori-fixed truncations with adaptive constructions.
- Results: For a given computational budget, basis selection is reported to produce more accurate PCEs than fixed a priori bases across high- and lower-dimensional problems.The paper also examines high-order terms, gradient information, and non-uniform random variables.
2. Polynomial chaos expansions
PCEs represent model inputs and outputs with orthonormal polynomial expansions whose basis is tied to the random-variable distribution. Because truncation is necessary and total-degree bases grow rapidly with dimension, the paper motivates adaptive alternatives.
- PCE formulation: PCEs represent model inputs and outputs as expansions of orthonormal multivariate polynomials in random variables.The tensor-product basis functions are orthonormal with respect to the random-vector distribution.
- PCE formulation: The polynomial family is chosen according to the input distribution, such as Legendre polynomials for uniformly distributed variables.The paper assumes the germ and input variables share a distribution up to a linear transformation.
- Convergence: Under sufficient regularity, analytical response surfaces can yield exponential convergence of the PCE in the L2(ρ(ξ))-sense.The convergence rate depends on the regularity of the response surface.
- Truncation: Truncation retains only polynomial terms satisfying a degree constraint, commonly using a total-degree basis indexed by ∥λ∥q ≤ p.The expansion must be truncated in practice before coefficient estimation.
- Truncation: The number of total-degree terms grows factorially with dimension, limiting use to moderate dimensions or low degrees in higher dimensions.This growth motivates alternatives to fixed total-degree truncations.
- Truncation: Hyperbolic index sets reduce basis size but omit interaction terms and may be inappropriate when those omitted terms have large PCE coefficients.Ideally, the truncation should adapt to the function being approximated.
3. ℓ1-minimization
ℓ1-minimization estimates PCE coefficients from limited, unstructured simulation data, but recovery depends strongly on basis truncation, sampling, and matrix properties. Increasing the basis can raise mutual coherence and RIP constants, reducing accuracy unless the sample budget also increases.
- Coefficient recovery: Given M unstructured model evaluations and a Vandermonde matrix Φ, ℓ1-minimization estimates the PCE coefficient vector α.The formulation uses a small set of realizations and corresponding model outputs to recover coefficients.
- Coefficient recovery: Basis Pursuit Denoising constrains the residual by ε, while ε = 0 gives Basis Pursuit; the formulation is closely related to LASSO.The tolerance controls the balance between fitting the data and regularizing the coefficient vector.
- Hyper-parameter estimation: Cross validation searches candidate hyper-parameters, such as polynomial degree p and tolerance ε, and selects the values minimizing cross-validation error.The procedure partitions the data into folds, trains on all but one fold, evaluates on the held-out fold, and minimizes the resulting error.
- Hyper-parameter estimation: Cross validation consistently selects a tolerance producing near-minimal ℓ2 error despite a bias toward underestimating that error.The reported example uses a fixed degree while ε decreases and compares cross-validation error with the resulting PCE error.
- Hyper-parameter estimation: Decreasing ε can cause over-fitting, whereas larger ε values can deteriorate approximation accuracy.The tolerance therefore has a direct accuracy trade-off in Basis Pursuit Denoising.
- Recoverability and truncation: For a fixed sample count, increasing the number of basis terms raises mutual coherence and RIP constants, making ℓ1-recovered PCEs less accurate.The reported six-dimensional Legendre example shows that higher-degree bases become beneficial only as the number of samples increases: p = 4 is best at M = 60, p = 7 at M = 120, and p = 8 at M = 240.
4. Iterative basis selection
The method uses PCE coefficient structure to adaptively grow anisotropic basis sets, selecting expansions through cross-validation to improve ℓ1-minimization while limiting unnecessary basis terms.
- Algorithm motivation: The algorithm leverages tree-like dependencies among PCE coefficients to identify large coefficients and improve their ℓ1-minimization estimates.Ancestor coefficient magnitudes are treated as indicators of child magnitudes, including in semi-connected trees.
- Algorithm overview: Basis selection proceeds through restriction, expansion, identification, and selection stages, as summarized in Algorithm 1 and Figure 6.The procedure repeatedly evaluates candidate basis sets during the adaptive construction.
- Algorithm overview: The initial basis is restricted to terms with non-zero coefficients, then expanded recursively up to T steps before ℓ1-minimization evaluates each candidate basis.Cross-validation chooses ε during each ℓ1-minimization solve, providing an expected-accuracy measure for the candidates.
- Basis selection: At each iteration, the candidate basis with the lowest cross-validation error is selected, while limiting expansion prevents degradation from rapidly increasing basis size.Increasing expansion steps can increase mutual coherence and reduce ℓ1-minimization performance, so the number of inner steps is chosen adaptively.
- Basis expansion: Expansion adds admissible forward neighbors whose backward neighbors exist in every dimension, targeting basis indices likely to have large coefficients.This admissibility rule preserves the required predecessor structure when adding terms.
5. Numerical examples
The numerical examples compare adaptive basis selection with fixed bases and an oracle across model classes, dimensions, coefficient regimes, gradients, and input distributions. Basis selection is most effective when coefficients decay rapidly or the model is anisotropic and compressible.
- Experimental setup: The experiments compare basis selection with a non-adaptive fixed-basis strategy and, where available, an approximately optimal oracle basis.The non-adaptive basis uses total-degree sets near a target cardinality, while the oracle selects terms with the largest exact PCE coefficients.
- 5.1. Algebraic test function: For the corner-peak function, basis selection is no worse than the non-adaptive method and improves relatively as anisotropy increases.Under strong anisotropy, it reaches the oracle's accuracy without the oracle's a priori truncation information.
- 5.1. Algebraic test function: Increasing anisotropy accelerates sorted PCE-coefficient decay, making the function more compressible and better suited to ℓ1-minimization with basis selection.The paper identifies coefficient-decay strength, rather than anisotropy itself, as the direct performance determinant.
- 5.2. Random oscillator: For the random oscillator, basis selection clearly outperforms the non-adaptive approach and produces results comparable to the oracle when coefficients decay rapidly.The reported improvement is associated with rapid decay of the exact PCE coefficients.
- 5.3. Diffusion equation: For the diffusion equation, basis selection shows negligible improvement because the exact PCE is not sufficiently compressible for ℓ1-minimization to be effective.Many coefficients have similar magnitudes, so neither basis selection nor the oracle offers much improvement over the non-adaptive strategy.
- Numerical comparisons: Basis selection remains significantly more accurate than the non-adaptive strategy in another test and produces results comparable to the approximately optimal oracle.The same qualitative advantage is observed in both cases reported for that example.
- 5.5. Gradient-enhanced ℓ1-minimization: Gradient information improves both adaptive and non-adaptive PCEs, while gradient-based PCE requires four times fewer samples for a given accuracy than function-value-only PCE.The fourfold reduction is close to the theoretical optimal factor of d/2 = 5 for the reported setting.
- 5.6. Non-uniform model inputs: Basis selection also retains its advantages for PCEs with non-uniform Gaussian random variables, although Hermite systems become poorly conditioned as sample size increases.The resulting non-monotone convergence motivates future sampling and pre-conditioning work for normal variables.
6. Conclusions
The paper concludes that adaptive basis selection improves ℓ1-based PCE approximation by focusing on likely large coefficients and limiting unimportant terms. Numerical examples support gains in high and low dimensions, with gradients, and for non-uniform random variables.
- 6. Conclusions: The method adaptively identifies large PCE coefficients and constructs anisotropic bases with more terms in important dimensions.It limits unimportant terms that increase mutual coherence and degrade ℓ1-minimization.
- 6. Conclusions: For a given computational budget, basis selection produces more accurate PCEs than bases fixed a priori.The conclusion is supported across the paper's numerical examples.
- 6. Conclusions: In high dimensions, basis selection identifies important high-order terms that low-order total-degree expansions cannot capture.The method is presented as useful where high-order total-degree bases are infeasible.
- 6. Conclusions: The method also improves results in lower-dimensional problems where high-order total-degree bases are feasible.The comparison remains against basis sets fixed a priori.
- 6. Conclusions: Basis selection can leverage function gradients and apply to PCEs with non-uniform random variables.The conclusion extends the demonstrated scope beyond Legendre polynomials with uniform variables.