Source-linked AI summary
A non-adapted sparse approximation of PDEs with stochastic inputs
Alireza Doostan, Houman Owhadi
TL;DR
The paper targets efficient uncertainty propagation for stochastic PDEs with many uncertain inputs, especially when intrusive solver modification is impractical. It uses non-intrusive, non-adapted compressive sampling to recover sparse polynomial-chaos approximations from direct solution samples, with probabilistic stability and convergence bounds. The approach is accurate when sparse representations exist, but may require more than N ≪P samples when the solution is not sparse.
Problem
Efficiently propagating uncertainty through systems with many uncertain sources remains difficult, and non-intrusive methods are important when sophisticated deterministic solvers cannot be readily modified.
Method
The method directly samples stochastic PDE solutions through a black-box deterministic solver and reconstructs sparse polynomial-chaos coefficients using ℓ0- or ℓ1-minimization.
Results
Probabilistic bounds establish stability and convergence, while ℓ1 recovery is accurate from sufficiently many random samples without prior knowledge of the coefficient sparsity pattern.
Takeaways & Limitations
The approach is suited to high-dimensional stochastic inputs and can use significantly fewer random solution samples than the full polynomial-chaos basis when the solution is sufficiently sparse.
Takeaways & Limitations
The method requires a sparse solution; without sparsity, it can converge but may not achieve N ≪P sample counts.
Abstract
from arXiv · showhide
We propose a method for the approximation of solutions of PDEs with stochastic coefficients based on the direct, i.e., non-adapted, sampling of solutions. This sampling can be done by using any legacy code for the deterministic problem as a black box. The method converges in probability (with probabilistic error bounds) as a consequence of sparsity and a concentration of measure phenomenon on the empirical correlation between samples. We show that the method is well suited for truly high-dimensional problems (with slow decay in the spectrum).
1 Introduction
The paper addresses uncertainty propagation for high-dimensional stochastic PDEs, where Monte Carlo is inefficient and non-intrusive methods must work with sophisticated deterministic solvers. It proposes compressive sampling of sparse polynomial-chaos representations without adapting to important stochastic dimensions.
- High-dimensional uncertainty propagation remains challenging because the curse of dimensionality is unresolved, while coupled deterministic solvers limit intrusive methods.
- Monte Carlo methods are generally inefficient for large-scale systems because of their slow convergence.
- The proposed approach directly samples PDE solutions and can use any legacy deterministic solver as a black box.
- The method is non-adapted, provably convergent with probabilistic error bounds, and designed for high-dimensional random inputs.
- Compressive sampling recovers sparse polynomial-chaos coefficients from N random samples when the stochastic function has only a small fraction of significant coefficients.
2 Problem setup
The paper formulates an elliptic PDE with uncertainty entering through a stochastic diffusion coefficient on a bounded Lipschitz domain. The coefficient is modeled probabilistically and subject to covariance and boundedness assumptions.
- The model is an elliptic stochastic PDE on a bounded Lipschitz domain D in dimensions 1, 2, or 3.
- Uncertainty enters through the stochastic diffusion coefficient a(x, ω), while the forcing term f(x) is deterministic.
- The diffusion coefficient is represented using a truncated Karhunen-Loève-like expansion based on covariance eigenpairs and its mean.
- The coefficient satisfies uniform almost-sure bounds 0 < a_min ≤ a(x, ω) ≤ a_max < ∞.
- The covariance function C_aa(x_1, x_2) is assumed piecewise analytic on D × D.
A-II.
The uncertainty variables are modeled as independent uniform coordinates, yielding a finite-dimensional parameterization of the PDE solution. The paper then introduces Legendre spectral discretization and compressive sampling for this representation.
- A-II.: The covariance regularity assumptions imply decay-rate bounds for the relevant expansion quantities, with algebraic decay possible under C^s(D × D) regularity.
- A-II.: The coordinates y_1, …, y_d are independent and uniformly distributed on [-1, 1], with joint density ρ(y).
- A-II.: The algorithm requires a sparse solution; assumption A-II only guarantees sparse-solution existence and is unnecessary when sparsity already exists.
- Finite-dimensional uncertainty implies a finite-dimensional representation u(x, y) of the PDE solution over D × Γ.
- The approach combines Legendre spectral stochastic discretization with compressive sampling to obtain the solution discretization.
3 Numerical approach
The numerical approach represents stochastic PDE solutions in a Legendre polynomial-chaos basis and recovers sparse coefficients from far fewer random solution samples than the basis size. Its stability and accuracy depend on coefficient sparsity and measurement-matrix coherence, with high-dimensional settings supporting N ≪ P under probabilistic guarantees.
- 3.1 Spectral stochastic discretization: The solution is approximated by a finite Legendre polynomial-chaos expansion whose coefficients are projections onto an orthonormal tensor-product basis.The finite truncation is refined by increasing polynomial order p, and the resulting approximation converges exponentially fast in mean square under the stated assumptions.
- 3.1 Spectral stochastic discretization: A solution with sparse polynomial-chaos coefficients can be accurately recovered from N ≪ P random samples, unlike least-squares regression, which normally requires N ≫ P samples.The samples are evaluations of the stochastic solution, while the measurement matrix contains corresponding basis evaluations.
- 3.2 Sparse recovery using compressive sampling: The recovery replaces the NP-hard minimum-support problem with ℓ1 minimization and extends it to error-tolerant formulations that accommodate polynomial-chaos truncation error.The BPDN formulation provides stable recovery when the truncated basis cannot represent the stochastic function exactly.
- 3.2 Sparse recovery using compressive sampling: Theorem 3.1 states that ℓ1 recovery is accurate and stable for essentially bounded stochastic functions admitting sparse Legendre expansions, without requiring prior knowledge of the coefficient support.The reconstruction error is controlled by the truncation residual and is proportional to the tolerance δ under the theorem's sampling conditions.
- 3.5.1 Mutual coherence of Ψ: Recovery quality is governed by coefficient sparsity and the mutual coherence of the random measurement matrix, which can be bounded with high probability as the sample count increases.The resulting sparse approximation also preserves exponential decay of the approximation error in the stated H1_0(D, L∞(Γ)) sense.
- 3.5.1 Mutual coherence of Ψ: N ∼ O(16P 4c_p,d ln P) ≪ P suffices when c_p,d < 1/4, a condition particularly suited to high-dimensional problems.The theoretical sample requirement also depends on the number S of dominant coefficients, and the stated bounds are acknowledged to be pessimistic in practice.
4 Numerical examples
The numerical experiments test sparse PC reconstruction for moderate- and high-dimensional stochastic diffusion coefficients, using sampled solutions and cross-validated truncation tolerances. BPDN and OMP recover solution statistics, with savings over isotropic sparse grids especially pronounced for d = 40.
- Test problems: The experiments use one-dimensional elliptic stochastic PDEs with diffusion dimensions d = 14 and d = 40, both with strictly positive coefficient realizations.The cases use (lc, d) = (1/5, 14) and (1/14, 40), with parameter choices ensuring positivity.
- Sampling and reconstruction: Solution samples at x = 0.5 are used to compute PC coefficients through ℓ1- and ℓ0-minimization, implemented with BPDN and OMP.The sample sizes are nested, recycling earlier samples as N increases.
- Sampling and reconstruction: The PC basis is refined with sample availability: N = {29, 120} uses p = 3 and P = 680, while larger N uses P = 1000 with selected fourth-order terms.The basis ordering prioritizes variables with smaller indices.
- Sampling and reconstruction: Cross-validation estimates δ by reconstructing coefficients on roughly 3N/4 samples and evaluating truncation error on the remaining validation samples across four replications.The selected tolerance minimizes the average validation error.
- Case I: d = 14: BPDN generally produces less sparse reconstructions than OMP, while OMP can overestimate some small coefficients because of truncation-error tolerance underestimation.The comparison uses reference coefficients from high-level stochastic collocation.
- Case II: d = 40: For d = 40, increasing N recovers more dominant PC coefficients, and sparse approximations require fewer samples than isotropic sparse-grid collocation for a given accuracy.The sample requirement depends more on the number of dominant PC terms than on the total basis size P.
5 Conclusion
The study proposes a non-intrusive, non-adapted compressive-sampling approach for recovering sparse polynomial-chaos representations of stochastic PDE solutions, with probabilistic convergence and stability guarantees.
- 5 Conclusion: The method recovers sparse stochastic PDE solutions from random samples using compressive sampling, without adapting the sampling process to the solution.It targets cases where few polynomial-chaos terms accurately represent the solution.
- 5 Conclusion: The implementation uses BPDN for ℓ1 minimization and OMP for ℓ0 minimization to construct sparse polynomial-chaos approximations.
- 5 Conclusion: Probabilistic bounds based on concentration of measure establish convergence and stability for the sparse constructions.
- 5 Conclusion: Applications to a linear elliptic PDE with high-dimensional random diffusion coefficients assess the proposed techniques in a setting with guaranteed polynomial-chaos sparsity.The recovery formalism is presented as applicable beyond elliptic PDEs.