Source-linked AI summary
Sparse Polynomial Chaos Expansions via Compressed Sensing and D-optimal Design
Paul Diaz, Alireza Doostan, Jerrad Hampton
TL;DR
Sparse PC approximation seeks accurate coefficient estimates while limiting costly model evaluations, but informative samples are difficult to choose when the coefficient support is unknown. The paper proposes DSP, which combines sequential design with D-optimality and coherence-oriented candidate sampling. The authors report more accurate approximations with less variability than non-sequential strategies under a fixed computational budget.
Problem
The paper asks how to choose samples strategically to improve sparse PC coefficient approximation when model evaluations are costly and the coefficient support is unknown.
Source: §4 · p. 11Method
DSP sequentially builds a D-optimal experimental design from a candidate pool, using support estimates from the iterative SP process.
Source: §4 · p. 11, §4.3 · p. 13Results
Sequential D-coherence-optimal sampling outperforms non-sequential strategies in PC approximation accuracy and variability for a fixed computational budget.
Source: §6 · p. 26Takeaways & Limitations
Coherence-optimal candidate sampling improves experimental designs and yields more stable, accurate PC coefficient approximations than standard Monte Carlo sampling.
Source: §6 · p. 26The initial design size is an educated guess rather than an established optimum, and it must contain at least 2K samples for the iteration's least-squares problem to be well-posed.
Source: §4.3 · pp. 13–14
Abstract
from arXiv · showhide
In the field of uncertainty quantification, sparse polynomial chaos (PC) expansions are commonly used by researchers for a variety of purposes, such as surrogate modeling. Ideas from compressed sensing may be employed to exploit this sparsity in order to reduce computational costs. A class of greedy compressed sensing algorithms use least squares minimization to approximate PC coefficients. This least squares problem lends itself to the theory of optimal design of experiments (ODE). Our work focuses on selecting an experimental design that improves the accuracy of sparse PC approximations for a fixed computational budget. We propose DSP, a novel sequential design, greedy algorithm for sparse PC approximation. The algorithm sequentially augments an experimental design according to a set of the basis polynomials deemed important by the magnitude of their coefficients, at each iteration. Our algorithm incorporates topics from ODE to estimate the PC coefficients. A variety of numerical simulations are performed on three physical models and manufactured sparse PC expansions to provide a comparative study between our proposed algorithm and other non-adaptive methods. Further, we examine the importance of sampling by comparing different strategies in terms of their ability to generate a candidate pool from which an optimal experimental design is chosen. It is demonstrated that the most accurate PC coefficient approximations, with the least variability, are produced with our design-adaptive greedy algorithm and the use of a studied importance sampling strategy. We provide theoretical and numerical results which show that using an optimal sampling strategy for the candidate pool is key, both in terms of accuracy in the approximation, but also in terms of constructing an optimal design.
1. Introduction
Sparse polynomial chaos expansions can reduce the number of model evaluations needed for uncertainty quantification, but selecting informative samples is challenging when the important coefficients are unknown. The paper proposes DSP, which uses optimal design within an iterative compressed-sensing method to build a sample design under a fixed computational budget.
1. Introduction
- For approximately sparse QoIs, compressed sensing can yield stable, convergent coefficient approximations from N < P samples when the measurement matrix meets specified conditions.Reducing QoI samples while maintaining accuracy and stability motivates the study.Source: §1 · p. 3
- DSP sequentially augments a design using an ODE criterion and coefficient-based support estimates, retaining selected samples because their QoI evaluations are costly.The method applies to SP and its general ideas may extend to OMP or CoSaMP.Source: §1 · p. 3
1.1. Contributions of this paper
- DSP reduces relative error and variability in approximated PC coefficients compared with standard SP, and optimal candidate-pool sampling benefits design construction and solution accuracy.The reported comparisons cover manufactured sparse expansions, a Duffing oscillator, the Ishigami function, and a wing weight function.Source: §1.1 · pp. 4–5
- Unlike prior sequential D-optimal design work that reported poor performance relative to other sampling techniques [41], this study reports improved accuracy and variability with its modified SP approach.The work uses SP rather than LAR and introduces QR with column pivoting to augment designs.Source: §1.1 · p. 4
2. Sampling
The section describes how sampling and weighting shape the least-squares subproblems used in sparse PC approximation. It contrasts standard sampling with coherence-optimal sampling, which is intended to improve stability and accuracy.
2.1. Sampling Preliminaries
- Sampling strategy determines the weights used in the least-squares system, while greedy compressed-sensing methods also solve over-determined least-squares subproblems.This connection motivates optimizing those subproblems through sampling choices.Source: §2.1 · p. 6
2.2. Standard sampling
- Standard Monte Carlo samples from the basis orthogonality measure and uses equal weights; coherence-optimal sampling instead seeks to minimize the coherence parameter.The described standard distributions are uniform for Legendre bases and standard normal for Hermite bases.Source: §2.2 · p. 6, §2.3 · p. 6
2.3. Coherence optimal sampling
- Coherence-optimal sampling improves stability and accuracy over standard sampling for sparse PC approximations using SP, with QoI sample counts scaling as N ∼ O(P log P).The stated scaling is linear in the number of PC coefficients up to a logarithmic factor.Source: §2.3 · p. 7
3. Optimal design of experiments
The section applies optimal design of experiments to least-squares subproblems in sparse PC approximation. It describes D-optimality, candidate-pool construction, a QR-based design heuristic, and theoretical properties relevant to the resulting designs.
3.2. Construction of alphabetic optimal designs
- Optimal designs can be selected before QoI evaluations because the information matrix does not depend on realized QoI values.This preprocessing is presented as cost-effective when model evaluations are the computational bottleneck.Source: §3.1 · p. 7, §3.2 · p. 8
3.1. D-optimal designs
- D-optimality maximizes the determinant of the information matrix, an estimation-oriented criterion intended to support precise coefficient estimation and surrogate accuracy.An equivalent formulation minimizes the determinant of the inverse information matrix.Source: §3.1 · p. 8
3.2. Construction of alphabetic optimal designs
- Exact D-optimal selection of N rows from M candidates is NP-hard, and common exchange and greedy methods can be costly because they search candidates exhaustively.The paper uses QR with column pivoting to avoid that exhaustive-search cost.Source: §3.2 · pp. 8–9
3.3. QR factorization with column pivoting on ΦT
- QR with column pivoting permutes candidate rows through a rank-revealing factorization, and the first N pivots define the selected design.Subset selection can produce a better-conditioned submatrix than RRQR alone, but requires both SVD and QR computations.Source: §3.3 · p. 9
3.4. Theory relevant for the design of experiments
- Coherence-optimal candidate sampling is proposed as a route to designs with larger φD than standard Monte Carlo candidate pools, with its theoretical discussion focused on subsets of K basis functions.The paper motivates this choice because modified SP selects designs from such submatrices.Source: §3.4 · p. 10
- RRQR pivoting yields designs with non-decreasing φD, and the paper reports that its resulting PC approximations consistently outperform random-column designs across varied QoIs.The guarantee is monotonicity during pivoting, not that the final design beats every random design in φD; RRQR is greedy and locally optimal.Source: §3.4 · p. 11
4. Improving Subspace Pursuit
The section proposes two improvements to sparse PC approximation with Subspace Pursuit: D-coherence-optimal candidate sampling and DSP, which sequentially augments a design using the current estimated support. It also describes RRQR-based augmentation, an initial-design choice, and cross-validation for selecting K.
4. Improving Subspace Pursuit
- Sequential design addresses the unknown support by starting with a relatively small design and adding samples according to the current estimated support, retaining samples already evaluated.This is motivated by costly simulations and the value of each computed QoI.Source: §4 · p. 11
4.1. Subspace pursuit with D-coherence-optimal sampling
- D-coherence-optimal sampling builds a candidate pool from coherence-optimal samples, then selects an N-point D-optimal design; the authors report it outperforms coherence-optimal sampling across a variety of problems.The method combines random candidate generation with deterministic design selection.Source: §4.1 · p. 12
4.2. Design adaptation using RRQR
- Design adaptation selects a candidate row by D-optimality using columns indexed by the current support estimate, and RRQR avoids explicitly computing rapidly growing determinants.The adaptation uses the support estimate from SP's least-squares step and considers only the corresponding submatrix.Source: §4.2 · p. 12
4.3. D-optimal Subspace Pursuit
- DSP updates the estimated support during SP, augments the design with one sample per iteration, and performs the final SP approximation after reaching the fixed evaluation budget.Unlike standard SP, which receives a complete measurement matrix and QoI values computed in advance, DSP forms the complete matrix only after selecting Nmax samples.Source: §4.3 · p. 13
- The initial design size N0 = max(2K, floor(0.8Nmax)) is an educated guess, not an optimum; it must be at least 2K for the LSA to be well-posed.An undersized start can produce an inaccurate support estimate and poor early D-optimal optimization.Source: §4.3 · pp. 13–14
4.4. Cross validation for K
- When K is unknown for an approximately sparse expansion, the proposed cross-validation procedure compares candidate K values using held-out QoI prediction error.It repeats random holdouts, averages validation errors for each K, and selects the K with the smallest mean error.Source: §4.4 · p. 14
5. Numerical Experiments
Across the tested models, sequential coherence-optimal design generally produced more accurate approximations with less variability than non-sequential alternatives. The experiments also compare how sampling strategies affect D-optimal candidate designs and sparse coefficient recovery.
5.1. The effects of sampling on D-optimal designs
- Across 1,000 experimental designs, coherence-optimal sampling yields slightly better D-optimal designs for d > p and is particularly advantageous for d < p, especially with Hermite polynomials, versus standard Monte Carlo sampling.Source: Figure 1 · p. 16, §5.1 · pp. 16–17, Figure 2 · p. 17
5.2. Manufactured sparse PC expansions
- Seq-D-Coh-Opt had the best mean error, error variability, and support recovery among the three strategies for manufactured sparse expansions.For standard Monte Carlo candidate pools, all three strategies instead produced unstable, inaccurate coefficient approximations.Source: §5.2 · pp. 18–19, Figure 3 · p. 18, Figure 4 · p. 19
5.3. A Nonlinear Duffing Oscillator
- D-Coh-Opt and Seq-D-Coh-Opt produced more accurate PC coefficient approximations with less variability than Coh-Opt, while Seq-D-Coh-Opt was slightly more accurate than non-sequential D-Coh-Opt.PC approximations using p = 12 achieved more accurate results than those using p = 9.Source: §5.3 · p. 22
5.4. The Wing Weight Function
- For the wing-weight model, Seq-D-Coh-Opt produced the most accurate approximations with the least variability, while D-Coh-Opt was only marginally better than Coh-Opt.The experiment used a 3rd-order expansion with 286 basis functions.Source: §5.4 · p. 23, Figure 9 · p. 23
5.5. The Ishigami Function
- For the Ishigami function, D-Coh-Opt and Seq-D-Coh-Opt were more accurate and less variable than Coh-Opt, particularly at larger expansion orders; sequential design also outperformed D-Coh-Opt.The sequential-versus-non-sequential improvement was greater than in the Duffing experiment.Source: Figure 10 · p. 24, §5.5 · p. 25, Figure 11 · p. 25
6. Conclusions and summary
The paper proposes DSP, which adapts D-optimal designs to the support estimates in sparse PC reconstruction, and compares it with non-sequential sampling strategies. Coherence-optimal sampling and sequential D-coherence-optimal sampling are reported to improve approximation accuracy and stability, especially for low-dimensional, high-order expansions.
6. Conclusions and summary
- DSP uses support estimates from SP iterations to adapt D-optimal designs for the over-determined least-squares problem within a fixed computational budget.The designs are constructed and updated using RRQR factorization.Source: §6 · pp. 25–26
- The numerical comparison covers manufactured sparse PC expansions, a Duffing oscillator, a wing weight function, and the Ishigami function.The study also compares standard Monte Carlo and coherence-optimal candidate pools.Source: §6 · p. 26
- Coherence-optimal sampling produces better experimental designs and more stable, accurate PC coefficient approximations than standard Monte Carlo sampling.Source: §6 · p. 26
- Sequential D-coherence-optimal sampling provides more accurate PC approximations with less variability than non-sequential D-Coh-Opt and Coh-Opt strategies at a fixed computational budget.The reported greatest improvements for Seq-D-Coh-Opt and D-Coh-Opt occur in low-dimension, high-order PC expansions.Source: §6 · p. 26
- The authors identify OMP and CoSaMP, along with other alphabetic optimality criteria, as directions for future work.Source: §6 · p. 26
Appendix A DSP Algorithm with Cross-validation for K
The appendix describes a modified DSP procedure that estimates K using cross-validation and updates the experimental design and coefficient support across iterations. It also invokes a Chernoff-type bound for coherence-optimal sampling.
Appendix A DSP Algorithm with Cross-validation for K
- The modified DSP procedure estimates K at initialization and, when the design size changes, re-estimates it during iteration.It begins with N0 = floor(0.8Nmax) samples and uses Algorithm 3 to estimate K.Source: Appendix A · pp. 26–27
- The proof of Theorem 3.1 uses a Chernoff-type bound for coherence-optimal sampling and presents the bound in terms of φD.The passage states that coherence-optimal sampling minimizes coherence μK over independent importance sampling distributions.Source: Appendix A · pp. 26–27
- At each iteration, DSP expands the candidate support, solves least squares on that support, retains the K largest coefficient entries, and adds a sample until Nmax.The algorithm stops if the residual norm increases after the stated iteration threshold; its output is the approximate PC coefficients on the selected support.Source: Appendix A · p. 27