Some greedy algorithms for sparse polynomial chaos expansions. (English) Zbl 1452.65012
Summary: 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 \(\nu\)-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.
MSC:
| 65C20 | Probabilistic models, generic numerical methods in probability and statistics |
| 62J05 | Linear regression; mixed models |
Keywords:
polynomial chaos; greedy algorithms; uncertainty quantification; compressed sensing; stochastic modelsSoftware:
CoSaMPReferences:
| [1] | Spanos, P. D.; Ghanem, R., Stochastic finite element expansion for random media, J. Eng. Mech., 115, 5, 1035-1053 (1989) |
| [2] | Xiu, D.; Karniadakis, G. E., The Wiener-Askey polynomial chaos for stochastic differential equations, SIAM J. Sci. Comput., 24, 2, 614-644 (2002) · Zbl 1014.65004 |
| [3] | Ernst, O. G.; Mugler, A.; Startkloff, H.-J.; Ullman, E., On the convergence of generalized polynomial chaos expansions, ESAIM: Modél. Math. Anal. Numér., 46, 317-339 (2012) · Zbl 1273.65012 |
| [4] | Babuška, I.; Tempone, R.; Zouraris, G. E., Galerkin finite element approximations of stochastic elliptic partial differential equations, SIAM J. Numer. Anal., 42, 2, 800-825 (2004) · Zbl 1080.65003 |
| [5] | Ghanem, R.; Spanos, P., A stochastic Galerkin expansion for nonlinear random vibration analysis, Probab. Eng. Mech., 8, 3-4, 255-264 (1993) |
| [6] | Xiu, D.; Shen, J., Efficient stochastic Galerkin methods for random diffusion equations, J. Comput. Phys., 228, 2, 266-281 (2009) · Zbl 1161.65008 |
| [7] | Matthies, H. G.; Keese, A., Galerkin methods for linear and nonlinear elliptic stochastic partial differential equations, Special Issue on Computational Methods in Stochastic Mechanics and Reliability Analysis. Special Issue on Computational Methods in Stochastic Mechanics and Reliability Analysis, Comput. Methods Appl. Mech. Eng., 194, 12-16, 1295-1331 (2005) · Zbl 1088.65002 |
| [8] | Eldred, M.; Burkardt, J., Comparison of non-intrusive polynomial chaos and stochastic collocation methods for uncertainty quantification, (Proceedings of the 47th AIAA Aerospace Sciences Meeting, vol. 976 (2009), AIAA), 1-20 |
| [9] | Blatman, G.; Sudret, B., Adaptive sparse polynomial chaos expansion based on least angle regression, J. Comput. Phys., 230, 6, 2345-2367 (2011) · Zbl 1210.65019 |
| [10] | Babuška, I.; Nobile, F.; Tempone, R., A stochastic collocation method for elliptic partial differential equations with random input data, SIAM Rev., 52, 2, 317-355 (2010) · Zbl 1226.65004 |
| [11] | Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge University Press |
| [12] | Natarajan, B. K., Sparse approximate solutions to linear systems, SIAM J. Comput., 24, 2, 227-234 (1995) · Zbl 0827.68054 |
| [13] | Doostan, A.; Owhadi, H., A non-adapted sparse approximation of PDEs with stochastic inputs, J. Comput. Phys., 230, 8, 3015-3034 (2011) · Zbl 1218.65008 |
| [14] | Tropp, J. A.; Gilbert, A. C., Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Inf. Theory, 53, 12, 4655-4666 (2007) · Zbl 1288.94022 |
| [15] | Candes, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted \(\ell_1\) minimization, J. Fourier Anal. Appl., 14, 5, 877-905 (2008) · Zbl 1176.94014 |
| [16] | Yang, X.; Karniadakis, G. E., Reweighted \(\ell_1\) minimization method for stochastic elliptic differential equations, J. Comput. Phys., 248, 87-108 (2013) · Zbl 1349.60113 |
| [17] | Jakeman, J.; Eldred, M.; Sargsyan, K., Enhancing \(\ell_1\)-minimization estimates of polynomial chaos expansions using basis selection, J. Comput. Phys., 289, 18-34 (2015) · Zbl 1352.65026 |
| [18] | Hampton, J.; Doostan, A., Compressive sampling of polynomial chaos expansions: convergence analysis and sampling strategies, J. Comput. Phys., 280, 363-386 (2015) · Zbl 1349.94110 |
| [19] | Jakeman, J. D.; Narayan, A.; Zhou, T., A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions, SIAM J. Sci. Comput., 39, 3, A1114-A1144 (2017) · Zbl 1368.65025 |
| [20] | Soize, C.; Ghanem, R., Physical systems with random uncertainties: chaos representations with arbitrary probability measure, SIAM J. Sci. Comput., 26, 2, 395-410 (2004) · Zbl 1075.60084 |
| [21] | Chkifa, A.; Cohen, A.; Migliorati, G.; Nobile, F.; Tempone, R., Discrete least squares polynomial approximation with random evaluations—application to parametric and stochastic elliptic PDEs, ESAIM: Modél. Math. Anal. Numér., 49, 3, 815-837 (2015) · Zbl 1318.41004 |
| [22] | Narayan, A.; Jakeman, J.; Zhou, T., A Christoffel function weighted least squares algorithm for collocation approximations, Math. Comput., 86, 306, 1913-1947 (2017) · Zbl 1361.65009 |
| [23] | Candes, E.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 |
| [24] | Pati, Y. C.; Rezaiifar, R.; Krishnaprasad, P. S., Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition, (1993 Conference Record of the Twenty-Seventh Asilomar Conference on Signals, Systems and Computers. 1993 Conference Record of the Twenty-Seventh Asilomar Conference on Signals, Systems and Computers, 1993 (1993), IEEE), 40-44 |
| [25] | Chen, S.; Billings, S. A.; Luo, W., Orthogonal least squares methods and their application to non-linear system identification, Int. J. Control, 50, 1873-1896 (1989) · Zbl 0686.93093 |
| [26] | Friedman, J. H.; Stuetzle, W., Projection pursuit regression, J. Am. Stat. Assoc., 817-823 (1981) |
| [27] | Mallat, S.; Zhang, Z., Matching pursuits with time-frequency dictionaries, IEEE Trans. Signal Process., 41, 12, 3397-3415 (1993) · Zbl 0842.94004 |
| [28] | Tropp, J., Greed is good: algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50, 10, 2231-2242 (2004) · Zbl 1288.94019 |
| [29] | Needell, D.; Vershynin, R., Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Top. Signal Process., 4, 2, 310-316 (2010) |
| [30] | Needell, D.; Tropp, J., CoSaMP: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003 |
| [31] | Donoho, D.; Tsaig, Y.; Drori, I.; Starck, J.-L., Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inf. Theory, 58, 2, 1094-1121 (2012) · Zbl 1365.94069 |
| [32] | Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inf. Theory, 55, 5, 2230-2249 (2009) · Zbl 1367.94082 |
| [33] | Donoho, D.; Elad, M.; Temlyakov, V., Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inf. Theory, 52, 1, 6-18 (2006) · Zbl 1288.94017 |
| [34] | Daniel, J. W.; Gragg, W. B.; Kaufman, L.; Stewart, G., Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comput., 30, 136, 772-795 (1976) · Zbl 0345.65021 |
| [35] | Golub, G.; Van Loan, C., Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (1996), Johns Hopkins University Press · Zbl 0865.65009 |
| [36] | Hammarling, S.; Lucas, C., Updating the QR Factorization and the Least Squares Problem (November 2008), Manchester Institute for Mathematics Sciences, Tech. rep. |
| [37] | Grote, M. J.; Huckle, T., Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput., 18, 3, 838-853 (1997) · Zbl 0872.65031 |
| [38] | Gould, N. I.M.; Scott, J. A., Sparse approximate-inverse preconditioners using norm-minimizing techniques, SIAM J. Sci. Comput., 19, 2, 605-625 (1998) · Zbl 0911.65037 |
| [39] | Smola, A. J.; Schölkopf, B., Sparse greedy matrix approximation for machine learning, (Proceedings of the Seventeenth International Conference on Machine Learning. Proceedings of the Seventeenth International Conference on Machine Learning, ICML ’00 (2000), Morgan Kaufmann Publishers Inc.), 911-918 |
| [40] | Molinaro, A. M.; Simon, R.; Pfeiffer, R. M., Prediction error estimation: a comparison of resampling methods, Bioinformatics, 21, 15, 3301-3307 (2005) |
| [41] | Donoho, D. L.; Elad, M.; Temlyakov, V. N., Stable Recovery of Sparse Overcomplete Representations in the Presence of Noise (2004), Stanford University, Department of Statistics, Tech. rep. |
| [42] | Hampton, J.; Doostan, A., Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression, Comput. Methods Appl. Mech. Eng., 290, 73-97 (2015) · Zbl 1426.62174 |
| [43] | Le Quéré, P., Accurate solutions to the square thermally driven cavity at high Rayleigh number, Comput. Fluids, 20, 1, 29-41 (1991) · Zbl 0731.76054 |
| [44] | Le Maître, O. P.; Reagan, M. T.; Najm, H. N.; Ghanem, R. G.; Knio, O. M., A stochastic projection method for fluid flow: II. Random process, J. Comput. Phys., 181, 1, 9-44 (2002) · Zbl 1052.76057 |
| [45] | Peng, J.; Hampton, J.; Doostan, A., A weighted \(\ell_1\)-minimization approach for sparse polynomial chaos expansions, J. Comput. Phys., 267, 92-111 (2014) · Zbl 1349.65198 |
| [46] | Holdeman, J. T.; Kim, J. W., Computation of incompressible thermal flows using Hermite finite elements, Comput. Methods Appl. Mech. Eng., 199, 49, 3297-3304 (2010) · Zbl 1225.76195 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
