Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies

The sensing matrices in Uncertainty Quantification are very structured and so it is sometimes difficult to use solvers relying on gaussian measurement matrices and one wonders if solvers different from L1 could be contemplated in light of the recent SwAMP thing. Anyway, today's paper investigate in a deep fashion this subject. Let us note the use of phase transition as a comparison tool, great !

Compressive Sampling of Polynomial Chaos Expansions: Convergence Analysis and Sampling Strategies by Jerrad Hampton, Alireza Doostan

Sampling orthogonal polynomial bases via Monte Carlo is of interest for uncertainty quantification of models with high-dimensional random inputs, using Polynomial Chaos (PC) expansions. It is known that bounding a probabilistic parameter, referred to as {\it coherence}, yields a bound on the number of samples necessary to identify coefficients in a sparse PC expansion via solution to an ℓ1-minimization problem. Utilizing asymptotic results for orthogonal polynomials, we bound the coherence parameter for polynomials of Hermite and Legendre type under the respective natural sampling distribution. In both polynomial bases we identify an importance sampling distribution which yields a bound with weaker dependence on the order of the approximation. For more general orthonormal bases, we propose the {\it coherence-optimal} sampling: a Markov Chain Monte Carlo sampling, which directly uses the basis functions under consideration to achieve a statistical optimality among all sampling schemes with identical support. We demonstrate these different sampling strategies numerically in both high-order and high-dimensional, manufactured PC expansions. In addition, the quality of each sampling method is compared in the identification of solutions to two differential equations, one with a high-dimensional random input and the other with a high-order PC expansion. In both cases the coherence-optimal sampling scheme leads to similar or considerably improved accuracy.

Relevant previous entry:

• Sunday Morning Insight: So what is missing in Compressive Imaging and Uncertainty Quantification ?
• Infinity Continues to Matter: Generalized sampling: stable reconstructions, inverse problems and compressed sensing over the continuum
• On the Convergence of Approximate Message Passing with Arbitrary Matrices
• The SwAMP Thing! Sparse Estimation with the Swept Approximated Message-Passing Algorithm -implementation -

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.