Some greedy algorithms for sparse polynomial chaos expansions

• Published in: Journal of computational physics 2019-06, Vol.387, p.303-325
• Main Authors: Baptista, Ricardo, Stolbunov, Valentin, Nair, Prasanth B.
• Format: Article
• Language: English
• Subjects: Algorithms; Basis functions; Compressed sensing; Computational physics; Dictionaries; Greedy algorithms; Iterative methods; Mathematical analysis; Personal computers; Polynomial chaos; Polynomials; Randomization; Set theory; Stochastic models; Uncertainty quantification
• ISSN: 0021-9991; 1090-2716
• DOI: 10.1016/j.jcp.2019.01.035

Compressed sensing algorithms approximate functions using limited evaluations by searching for a sparse representation among a dictionary of basis functions. Orthogonal matching pursuit (OMP) is a greedy algorithm for selecting basis functions whose computational cost scales with the size of the dictionary. For polynomial chaos (PC) approximations, the size of the dictionary grows quickly with the number of model inputs and the maximum polynomial degree, making them often prohibitive to use with greedy methods. We propose two new algorithms for efficiently constructing sparse PC expansions for problems with high-dimensional inputs. The first algorithm is a parallel OMP method coupled with an incremental QR factorization scheme, wherein the model construction step is interleaved with a ν-fold cross-validation procedure. The second approach is a randomized greedy algorithm that leverages a probabilistic argument to only evaluate a subset of basis functions from the dictionary at each iteration of the incremental algorithm. The randomized algorithm is demonstrated to recover model outputs with a similar level of sparsity and accuracy as OMP, but with a cost that is independent of the dictionary size. Both algorithms are validated with a numerical comparison of their performance on a series of algebraic test problems and PDEs with high-dimensional inputs. •We consider the problem of efficiently learning sparse polynomial chaos expansions.•A novel parallelization strategy is proposed.•A randomized greedy algorithm is developed to handle large-scale problems.•A detailed theoretical analysis is carried out to evaluate the proposed algorithms.