Source-linked AI summary
A weighted L1-minimization approach for sparse polynomial chaos expansions
Ji Peng, Jerrad Hampton, Alireza Doostan
TL;DR
High-dimensional stochastic functions require sparse PC approximations from limited non-adapted samples, but standard recovery can be hindered by many small coefficients. The paper uses coefficient-decay information to form weighted ℓ1 minimization, establishes convergence guarantees, and finds better performance than unweighted and iteratively reweighted alternatives in two stochastic PDE tests.
Problem
High-dimensional PC coefficient estimation is challenging because conventional approaches can require exponentially many samples, while small coefficients can inhibit accurate recovery of larger ones.
Method
The paper modifies BPDN by weighting the ℓ1 penalty using a priori PC-coefficient decay information, including analytical estimates and bounds derived from dimensional analysis.
Results
The weighted approach has analytical convergence guarantees and outperforms unweighted ℓ1 minimization in both a random-coefficient elliptic problem and a stochastic cavity-flow problem, with better accuracy than iteratively reweighted ℓ1.
Takeaways & Limitations
Coefficient-decay information can be used to construct weighted norms that improve sparse PC approximations when such information is available.
Takeaways & Limitations
The numerical and analytical results use Legendre PC expansions, and one coefficient-bound assumption may not remain reasonable for other flow parameters such as larger Ra numbers.
Abstract
from arXiv · showhide
This work proposes a method for sparse polynomial chaos (PC) approximation of high-dimensional stochastic functions based on non-adapted random sampling. We modify the standard l1 -minimization algorithm, originally proposed in the context of compressive sampling, using a priori information about the decay of the PC coefficients and refer to the resulting algorithm as weighted l1 -minimization. We provide conditions under which we may guarantee recovery using this weighted scheme. Numerical tests are used to compare the weighted and non-weighted methods for the recovery of solutions to two differential equations with high-dimensional random inputs: a boundary value problem with a random elliptic operator and a 2-D thermally driven cavity flow with random boundary condition.
1. Introduction
High-dimensional uncertainty quantification motivates sparse polynomial chaos approximations from few non-adapted samples. The paper modifies BPDN by weighting coefficients according to a priori decay information to improve recovery of the largest PC coefficients.
- Polynomial chaos representation: A finite-variance quantity of interest with independent random inputs admits a polynomial chaos expansion in orthonormal polynomial basis functions.The expansion represents the uncertain output through PC coefficients multiplying basis functions of the random input.
- Motivation: High-dimensional stochastic inputs make collocation and regression sample requirements grow exponentially with input dimension, motivating compressive sampling.Monte Carlo also converges slowly, while sparse PC representations seek accurate reconstruction with few samples.
- Compressive recovery: BPDN replaces computationally expensive ℓ0 minimization with a convex ℓ1 relaxation for recovering approximately sparse PC coefficients.The ℓ0 problem directly seeks the sparsest approximation but has cost growing exponentially in the truncated basis size P.
- Compressive recovery: Cross-validation selects the data-misfit tolerance because fitting observed samples alone may fail to approximate the quantity of interest at unobserved inputs.Too-small tolerances can overfit the sampled data, while the paper uses cross-validation to choose ǫ.
- Weighted approach: Weighted ℓ1-minimization incorporates prior estimates of PC-coefficient decay to penalize small coefficients more strongly and enhance recovery of larger coefficients.The approach is motivated by analytical decay estimates or relations among physical variables and is accompanied by theoretical results for the weighted problem.
2. Problem Statement and Solution Approach
The paper reconstructs solutions of stochastic PDEs by fitting truncated polynomial chaos expansions to solver evaluations at random input realizations. Approximate sparsity reduces the coefficient-estimation burden, while weighted ℓ1 recovery uses coefficient-dependent penalties.
- Problem formulation: The stochastic PDE input is modeled by an independent random vector, with uncertainty entering parameters such as diffusion coefficients, boundary conditions, or initial conditions.A fixed numerical solver evaluates the solution for sampled realizations of the random input.
- Problem formulation: The experiments consider a random-coefficient elliptic boundary value problem and a two-dimensional thermally driven cavity flow with a random boundary condition.These cases test recovery of stochastic PDE solutions from non-intrusive solver evaluations.
- Polynomial chaos approximation: Polynomial chaos basis functions are formed from products of univariate orthonormal polynomials and truncated to P total-degree basis functions for computation.The main setup assumes uniformly distributed inputs and orthonormal Legendre polynomials, while noting applicability to other orthonormal bases.
- Sparse PC expansion: Approximate sparsity allows the basis to be reduced from P functions to a small active set C, decreasing the number of coefficients and solution realizations needed.When |C| < N, estimating the active coefficients is less prone to overfitting and is well-posed when the restricted sampling matrix has full rank.
- Weighted recovery: Weighted recovery modifies ℓ1 minimization by assigning nonnegative diagonal weights to individual PC coefficients based on prior information.The weighted formulation changes the penalty while retaining the compressive-sampling recovery framework.
3. Weighted ℓ1-minimization
The paper weights the ℓ1 objective using prior estimates of polynomial-chaos coefficient decay, then analyzes recovery conditions and practical trade-offs. Weighted recovery can favor important coefficients, but its guarantees do not by themselves establish superiority over standard ℓ1-minimization.
- Weighted formulation: Weighted ℓ1-minimization changes the standard problem by applying a diagonal weight matrix W while retaining the same solver.The transformation uses weighted coefficients and can be implemented through a modified measurement matrix.
- Setting weights wj: Weights are chosen inversely to anticipated coefficient magnitudes: large expected coefficients receive smaller penalties, while less important coefficients receive larger weights.The parameter p controls weight dispersion and represents confidence in the anticipated coefficient magnitudes.
- Setting weights wj: The approach uses prior coefficient-decay information for linear elliptic problems and physical dependencies for a nonlinear 2-D Navier–Stokes problem.Its success depends on identifying relative coefficient importance rather than estimating exact coefficient values.
- Theoretical recovery via weighted ℓ1-minimization: The restricted-isometry analysis assumes δ3s + 3δ4s < 2 for approximate s-sparse solutions and bounds recovery under weighted ℓ1-minimization.The analysis relates weighted recovery to standard sparse-recovery conditions, but does not conclusively compare weighted and standard ℓ1 accuracy.
- Theoretical recovery via weighted ℓ1-minimization: With no truncation error, the analysis may verify sparsity of a computed solution recovering u, but does not guarantee that the sparsest solution has been found.The recovered solution is close to u rather than necessarily identical to the sparsest feasible solution.
- Theoretical recovery via weighted ℓ1-minimization: If βW < 1, the weighted recovery theorem guarantees the stated recovery result for solutions of the weighted problem, while βW ≥ 1 can make the condition fail sharply.The quantity βW is presented as a weight-quality measure, with smaller values preferred.
4. Numerical examples
The numerical examples assess weighted ℓ1-minimization on elliptic and thermally driven cavity-flow problems with random inputs. Across both problems, prior coefficient-decay information generally improves sparse recovery for small sample sizes, while its usefulness depends on the quality and assumptions of the estimates.
- 4.1. Elliptic equation: The elliptic test uses a one-dimensional random elliptic equation with d = 40 and P = 2500 Legendre PC basis functions.The expansion uses an incomplete third-order truncation.
- 4.1.1. Setting weights wj: Analytical coefficient-decay bounds provide a reasonable estimate for setting weights, although some second- and third-degree coefficients decay more slowly than predicted.The bounds are obtained from the analytical estimate in (21) and compared with reference coefficients.
- 4.1.2. Results: For small sample sizes, weighted ℓ1-minimization outperforms non-weighted ℓ1-minimization and both ℓ1 methods outperform sparse-grid collocation on standard deviation and rms errors.The comparison uses N = {81, 200, 1000} and 100 independent replications for each sample size.
- 4.1.2. Results: Weighted least-squares regression is sensitive to coefficient-bound quality because selecting an incorrect subset C can reduce accuracy.The tested subset contains up to ⌊N/2⌋ indices associated with the largest estimated coefficient bounds.
- 4.2.1. Approximate bound on PC coefficients: Qualitatively accurate coefficient bounds are sufficient for weighted ℓ1-minimization to improve accuracy at small N, but the bounds rely on a strong functional-derivative assumption.The authors warn that this assumption may be unsuitable for other problems or larger Ra numbers.
- 4.2.2. Results: For the cavity flow, weighted ℓ1-minimization performs best particularly at N = 41 and is relatively insensitive to the tested ϵw values.The best performance occurs at ϵw = 5 × 10^-4 · ĉ1, while iteratively re-weighted ℓ1-minimization can lose accuracy at N = 1000 for some settings.
- 4.2.2. Results: In the cavity-flow comparison, sparse-grid collocation performs poorly because higher-order PC modes contribute substantially, while weighted least-squares selects some basis functions incorrectly.These effects are reported in the coefficient and rms-error comparisons.
5. Conclusion
The paper introduces weighted ℓ1-minimization for sparse polynomial chaos expansions, using a priori coefficient information to improve recovery and providing analytical convergence guarantees. Across two stochastic differential-equation test cases, the weighted approach outperforms non-weighted and iteratively reweighted alternatives, while its demonstrated theory and experiments are primarily based on Legendre expansions.
- Weighted ℓ1-minimization uses a priori knowledge of PC-coefficient decay to enhance standard ℓ1-minimization for sparse PC expansions.The information may come from analytical decay or dimensional analysis and is used to penalize small coefficients more strongly.
- Analytical results guarantee convergence of the weighted ℓ1-minimization approach.
- Across two test cases, weighted ℓ1-minimization outperforms non-weighted ℓ1-minimization and achieves better accuracy than iteratively reweighted ℓ1-minimization.The tests involve a linear elliptic equation with random coefficient and a thermally driven flow with stochastic temperature boundary condition.
- Iteratively reweighted ℓ1-minimization is sensitive to its weight-defining parameter, whereas weighted ℓ1-minimization is comparatively less sensitive.
- The demonstrated numerical and analytical results use Legendre PC expansions, although the approach may extend to Hermite or Jacobi polynomial bases.