Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2022 | OriginalPaper | Buchkapitel

Towards Optimal Sampling for Learning Sparse Approximations in High Dimensions

verfasst von: Ben Adcock, Juan M. Cardenas, Nick Dexter, Sebastian Moraga

Erschienen in: High-Dimensional Optimization and Probability

Verlag: Springer International Publishing

share
TEILEN

Abstract

In this chapter, we discuss recent work on learning sparse approximations to high-dimensional functions on data, where the target functions may be scalar-,’ vector- or even Hilbert space-valued. Our main objective is to study how the sampling strategy affects the sample complexity—that is, the number of samples that suffice for accurate and stable recovery—and to use this insight to obtain optimal or near-optimal sampling procedures. We consider two settings. First, when a target sparse representation is known, in which case we present a near-complete answer based on drawing independent random samples from carefully designed probability measures. Second, we consider the more challenging scenario when such representation is unknown. In this case, while not giving a full answer, we describe a general construction of sampling measures that improves over standard Monte Carlo sampling. We present examples using algebraic and trigonometric polynomials, and for the former, we also introduce a new procedure for function approximation on irregular (i.e. nontensorial) domains. The effectiveness of this procedure is shown through numerical examples. Finally, we discuss a number of structured sparsity models and how they may lead to better approximations.
Literatur
1.
Zurück zum Zitat B. Adcock, Infinite-dimensional ℓ 1 minimization and function approximation from pointwise data. Constr. Approx. 45(3), 343–390 (2017) MathSciNetCrossRef B. Adcock, Infinite-dimensional 1 minimization and function approximation from pointwise data. Constr. Approx. 45(3), 343–390 (2017) MathSciNetCrossRef
2.
3.
Zurück zum Zitat B. Adcock, S. Brugiapaglia, Sparse approximation of multivariate functions from small datasets via weighted orthogonal matching pursuit, in Spectral and High Order Methods for Partial Differential Equations ICOSAHOM 2018, vol. 134 of Lect. Notes Comput. Sci. Eng., ed. by S. Sherwin, D. Moxey, J. Peiró, P. Vincent, C. Schwab (Springer, Cham, Switzerland, 2020), pp. 611–621 CrossRef B. Adcock, S. Brugiapaglia, Sparse approximation of multivariate functions from small datasets via weighted orthogonal matching pursuit, in Spectral and High Order Methods for Partial Differential Equations ICOSAHOM 2018, vol. 134 of Lect. Notes Comput. Sci. Eng., ed. by S. Sherwin, D. Moxey, J. Peiró, P. Vincent, C. Schwab (Springer, Cham, Switzerland, 2020), pp. 611–621 CrossRef
4.
Zurück zum Zitat B. Adcock, J.M. Cardenas, Near-optimal sampling strategies for multivariate function approximation on general domains. SIAM J. Math. Data Sci. 2(3), 607–630 (2020) MathSciNetMATHCrossRef B. Adcock, J.M. Cardenas, Near-optimal sampling strategies for multivariate function approximation on general domains. SIAM J. Math. Data Sci. 2(3), 607–630 (2020) MathSciNetMATHCrossRef
5.
Zurück zum Zitat B. Adcock, A.C. Hansen, Compressive Imaging: Structure, Sampling, Learning (Cambridge University Press, Cambridge, UK, 2021) MATHCrossRef B. Adcock, A.C. Hansen, Compressive Imaging: Structure, Sampling, Learning (Cambridge University Press, Cambridge, UK, 2021) MATHCrossRef
6.
7.
Zurück zum Zitat B. Adcock, Y. Sui, Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements. Constr. Approx. 50, 167–207 (2019) MathSciNetMATHCrossRef B. Adcock, Y. Sui, Compressive Hermite interpolation: sparse, high-dimensional approximation from gradient-augmented measurements. Constr. Approx. 50, 167–207 (2019) MathSciNetMATHCrossRef
8.
Zurück zum Zitat B. Adcock, S. Brugiapaglia, C.G. Webster, Compressed sensing approaches for polynomial approximation of high-dimensional functions, in Compressed Sensing and its Applications: Second International MATHEON Conference 2015, Appl. Numer. Harmon. Anal., ed. by H. Boche, G. Caire, R. Calderbank, M. März, G. Kutyniok, R. Mathar (Birkhäuser, Cham, Switzerland, 2017), pp. 93–124 CrossRef B. Adcock, S. Brugiapaglia, C.G. Webster, Compressed sensing approaches for polynomial approximation of high-dimensional functions, in Compressed Sensing and its Applications: Second International MATHEON Conference 2015, Appl. Numer. Harmon. Anal., ed. by H. Boche, G. Caire, R. Calderbank, M. März, G. Kutyniok, R. Mathar (Birkhäuser, Cham, Switzerland, 2017), pp. 93–124 CrossRef
9.
Zurück zum Zitat B. Adcock, A. Bao, J. D. Jakeman, A. Narayan, Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations. SIAM/ASA J. Uncertain. Quantif. 6(4), 1424–1453 (2018) MathSciNetMATHCrossRef B. Adcock, A. Bao, J. D. Jakeman, A. Narayan, Compressed sensing with sparse corruptions: fault-tolerant sparse collocation approximations. SIAM/ASA J. Uncertain. Quantif. 6(4), 1424–1453 (2018) MathSciNetMATHCrossRef
10.
Zurück zum Zitat B. Adcock, A. Bao, S. Brugiapaglia, Correcting for unknown errors in sparse high-dimensional function approximation. Numer. Math. 142(3), 667–711 (2019) MathSciNetMATHCrossRef B. Adcock, A. Bao, S. Brugiapaglia, Correcting for unknown errors in sparse high-dimensional function approximation. Numer. Math. 142(3), 667–711 (2019) MathSciNetMATHCrossRef
11.
Zurück zum Zitat B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, Deep neural networks are effective at learning high-dimensional Hilbert-valued functions from limited data, in Proceedings of The Second Annual Conference on Mathematical and Scientific Machine Learning, vol. 145 of Proc. Mach. Learn. Res. (PMLR), ed. by J. Bruna, J. S. Hesthaven, L. Zdeborová (PMLR, 2021), pp. 1–36 B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, Deep neural networks are effective at learning high-dimensional Hilbert-valued functions from limited data, in Proceedings of The Second Annual Conference on Mathematical and Scientific Machine Learning, vol. 145 of Proc. Mach. Learn. Res. (PMLR), ed. by J. Bruna, J. S. Hesthaven, L. Zdeborová (PMLR, 2021), pp. 1–36
12.
Zurück zum Zitat B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, On efficient algorithms for computing near-optimal polynomial approximations of smooth, high-dimensional Hilbert-valued functions from sample values. In Preparation (2021) B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, On efficient algorithms for computing near-optimal polynomial approximations of smooth, high-dimensional Hilbert-valued functions from sample values. In Preparation (2021)
13.
Zurück zum Zitat B. Adcock, S. Brugiapaglia, C.G. Webster, Sparse Polynomial Approximation of High-Dimensional Functions (Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2022) MATHCrossRef B. Adcock, S. Brugiapaglia, C.G. Webster, Sparse Polynomial Approximation of High-Dimensional Functions (Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2022) MATHCrossRef
14.
Zurück zum Zitat N. Alemazkoor, H. Meidani, Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions. Comput. Methods Appl. Mech. Eng. 318, 937–956 (2017) MathSciNetMATHCrossRef N. Alemazkoor, H. Meidani, Divide and conquer: an incremental sparsity promoting compressive sampling approach for polynomial chaos expansions. Comput. Methods Appl. Mech. Eng. 318, 937–956 (2017) MathSciNetMATHCrossRef
15.
Zurück zum Zitat N. Alemazkoor, H. Meidani, A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions. J. Comput. Phys. 371, 137–151 (2018) MathSciNetMATHCrossRef N. Alemazkoor, H. Meidani, A near-optimal sampling strategy for sparse recovery of polynomial chaos expansions. J. Comput. Phys. 371, 137–151 (2018) MathSciNetMATHCrossRef
16.
Zurück zum Zitat B. Arras, M. Bachmayr, A. Cohen, Sequential sampling for optimal weighted least squares approximations in hierarchical spaces. SIAM J. Math. Data Sci. 1(1), 189–207 (2019) MathSciNetMATHCrossRef B. Arras, M. Bachmayr, A. Cohen, Sequential sampling for optimal weighted least squares approximations in hierarchical spaces. SIAM J. Math. Data Sci. 1(1), 189–207 (2019) MathSciNetMATHCrossRef
17.
Zurück zum Zitat J. Bäck, F. Nobile, L. Tamellini, R. Tempone, Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison, in Spectral and High Order Methods for Partial Differential Equations, vol. 76 of Lect. Notes Comput. Sci. Eng., ed. by J.S. Hesthaven, E.M. Rønquist (Springer, Berlin, Heidelberg, Germany, 2011), pp. 43–62 CrossRef J. Bäck, F. Nobile, L. Tamellini, R. Tempone, Stochastic spectral Galerkin and collocation methods for PDEs with random coefficients: a numerical comparison, in Spectral and High Order Methods for Partial Differential Equations, vol. 76 of Lect. Notes Comput. Sci. Eng., ed. by J.S. Hesthaven, E.M. Rønquist (Springer, Berlin, Heidelberg, Germany, 2011), pp. 43–62 CrossRef
18.
Zurück zum Zitat G. Blatman, B. Sudret, Adaptive sparse polynomial chaos expansion based on least angle regression. J. Comput. Phys. 230, 2345–2367 (2011) MathSciNetMATHCrossRef G. Blatman, B. Sudret, Adaptive sparse polynomial chaos expansion based on least angle regression. J. Comput. Phys. 230, 2345–2367 (2011) MathSciNetMATHCrossRef
19.
Zurück zum Zitat J.-L. Bouchot, H. Rauhut, C. Schwab, Multi-level compressed sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs (2017). arXiv:1701.01671 J.-L. Bouchot, H. Rauhut, C. Schwab, Multi-level compressed sensing Petrov-Galerkin discretization of high-dimensional parametric PDEs (2017). arXiv:1701.01671
20.
Zurück zum Zitat S. Brugiapaglia, S. Dirksen, H.C. Jung, H. Rauhut, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Appl. Comput. Harmon. Anal. 53, 231–269 (2021) MathSciNetMATHCrossRef S. Brugiapaglia, S. Dirksen, H.C. Jung, H. Rauhut, Sparse recovery in bounded Riesz systems with applications to numerical methods for PDEs. Appl. Comput. Harmon. Anal. 53, 231–269 (2021) MathSciNetMATHCrossRef
21.
Zurück zum Zitat A. Chkifa, A. Cohen, R. DeVore, C. Schwab, Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs. ESAIM. Math. Model. Numer. Anal. 47(1), 253–280 (2013) MathSciNetMATHCrossRef A. Chkifa, A. Cohen, R. DeVore, C. Schwab, Sparse adaptive Taylor approximation algorithms for parametric and stochastic elliptic PDEs. ESAIM. Math. Model. Numer. Anal. 47(1), 253–280 (2013) MathSciNetMATHCrossRef
22.
Zurück zum Zitat A. Chkifa, A. Cohen, C. Schwab, High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs. Found. Comput. Math. 14(4), 601–633 (2014) MathSciNetMATHCrossRef A. Chkifa, A. Cohen, C. Schwab, High-dimensional adaptive sparse polynomial interpolation and applications to parametric PDEs. Found. Comput. Math. 14(4), 601–633 (2014) MathSciNetMATHCrossRef
23.
Zurück zum Zitat A. Chkifa, A. Cohen, G. Migliorati, F. Nobile, R. Tempone, Discrete least squares polynomial approximation with random evaluations – application to parametric and stochastic elliptic PDEs. ESAIM. Math. Model. Numer. Anal. 49(3), 815–837 (2015) MathSciNetMATHCrossRef A. Chkifa, A. Cohen, G. Migliorati, F. Nobile, R. Tempone, Discrete least squares polynomial approximation with random evaluations – application to parametric and stochastic elliptic PDEs. ESAIM. Math. Model. Numer. Anal. 49(3), 815–837 (2015) MathSciNetMATHCrossRef
24.
Zurück zum Zitat A. Chkifa, A. Cohen, C. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs. J. Math. Pures Appl. 103, 400–428 (2015) MathSciNetMATHCrossRef A. Chkifa, A. Cohen, C. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs. J. Math. Pures Appl. 103, 400–428 (2015) MathSciNetMATHCrossRef
25.
Zurück zum Zitat A. Chkifa, N. Dexter, H. Tran, C.G. Webster, Polynomial approximation via compressed sensing of high-dimensional functions on lower sets. Math. Comput. 87(311), 1415–1450 (2018) MathSciNetMATHCrossRef A. Chkifa, N. Dexter, H. Tran, C.G. Webster, Polynomial approximation via compressed sensing of high-dimensional functions on lower sets. Math. Comput. 87(311), 1415–1450 (2018) MathSciNetMATHCrossRef
26.
Zurück zum Zitat B. Choi, M.A. Iwen, F. Krahmer, Sparse harmonic transforms: A new class of sublinear-time algorithms for learning functions of many variables. Found. Comput. Math. 21(2), 275–329 (2021) MathSciNetMATHCrossRef B. Choi, M.A. Iwen, F. Krahmer, Sparse harmonic transforms: A new class of sublinear-time algorithms for learning functions of many variables. Found. Comput. Math. 21(2), 275–329 (2021) MathSciNetMATHCrossRef
27.
Zurück zum Zitat O. Christensen, An Introduction to Frames and Riesz Bases, 2nd edn. (Appl. Numer. Harmon. Anal. Birkhäuser, Basel, Switzerland, 2016) O. Christensen, An Introduction to Frames and Riesz Bases, 2nd edn. (Appl. Numer. Harmon. Anal. Birkhäuser, Basel, Switzerland, 2016)
29.
Zurück zum Zitat A. Cohen, M. Dolbeault, Optimal pointwise sampling for L 2 approximation (2021). arXiv:2105.05545 A. Cohen, M. Dolbeault, Optimal pointwise sampling for L 2 approximation (2021). arXiv:2105.05545
31.
Zurück zum Zitat A. Cohen, G. Migliorati, Multivariate approximation in downward closed polynomial spaces, in Contemporary Computational Mathematics – A Celebration of the 80th Birthday of Ian Sloan, ed. by J. Dick, F.Y. Kuo, H. Woźniakowski (Springer, Cham, Switzerland, 2018), pp. 233–282 CrossRef A. Cohen, G. Migliorati, Multivariate approximation in downward closed polynomial spaces, in Contemporary Computational Mathematics – A Celebration of the 80th Birthday of Ian Sloan, ed. by J. Dick, F.Y. Kuo, H. Woźniakowski (Springer, Cham, Switzerland, 2018), pp. 233–282 CrossRef
32.
Zurück zum Zitat A. Cohen, R.A. DeVore, C. Schwab, Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s. Anal. Appl. (Singap.) 9(1), 11–47 (2011) A. Cohen, R.A. DeVore, C. Schwab, Analytic regularity and polynomial approximation of parametric and stochastic elliptic PDE’s. Anal. Appl. (Singap.) 9(1), 11–47 (2011)
33.
Zurück zum Zitat A. Cohen, M.A. Davenport, D. Leviatan, On the stability and accuracy of least squares approximations. Found. Comput. Math. 13, 819–834 (2013) MathSciNetMATHCrossRef A. Cohen, M.A. Davenport, D. Leviatan, On the stability and accuracy of least squares approximations. Found. Comput. Math. 13, 819–834 (2013) MathSciNetMATHCrossRef
34.
Zurück zum Zitat A. Cohen, G. Migliorati, F. Nobile, Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension. Constr. Approx. 45, 497–519 (2017) MathSciNetMATHCrossRef A. Cohen, G. Migliorati, F. Nobile, Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension. Constr. Approx. 45, 497–519 (2017) MathSciNetMATHCrossRef
35.
Zurück zum Zitat D. Dũng, V. Temlyakov, T. Ullrich, Hyperbolic Cross Approximation. Adv. Courses Math. CRM Barcelona (Birkhäuser, Basel, Switzerland, 2018) D. Dũng, V. Temlyakov, T. Ullrich, Hyperbolic Cross Approximation. Adv. Courses Math. CRM Barcelona (Birkhäuser, Basel, Switzerland, 2018)
36.
Zurück zum Zitat N. Dexter, H. Tran, C. Webster, A mixed ℓ 1 regularization approach for sparse simultaneous approximation of parameterized PDEs. ESAIM. Math. Model. Numer. Anal. 53, 2025–2045 (2019) MathSciNetMATHCrossRef N. Dexter, H. Tran, C. Webster, A mixed 1 regularization approach for sparse simultaneous approximation of parameterized PDEs. ESAIM. Math. Model. Numer. Anal. 53, 2025–2045 (2019) MathSciNetMATHCrossRef
37.
Zurück zum Zitat P. Diaz, A. Doostan, J. Hampton, Sparse polynomial chaos expansions via compressed sensing and D-optimal design. Comput. Methods Appl. Mech. Eng. 336, 640–666 (2018) MathSciNetMATHCrossRef P. Diaz, A. Doostan, J. Hampton, Sparse polynomial chaos expansions via compressed sensing and D-optimal design. Comput. Methods Appl. Mech. Eng. 336, 640–666 (2018) MathSciNetMATHCrossRef
38.
Zurück zum Zitat M. Dolbeault, A. Cohen, Optimal sampling and Christoffel functions on general domains (2020). arXiv:2010.11040 M. Dolbeault, A. Cohen, Optimal sampling and Christoffel functions on general domains (2020). arXiv:2010.11040
39.
Zurück zum Zitat A. Doostan, H. Owhadi, A non-adapted sparse approximation of PDEs with stochastic inputs. J. Comput. Phys. 230(8), 3015–3034 (2011) MathSciNetMATHCrossRef A. Doostan, H. Owhadi, A non-adapted sparse approximation of PDEs with stochastic inputs. J. Comput. Phys. 230(8), 3015–3034 (2011) MathSciNetMATHCrossRef
40.
Zurück zum Zitat O.G. Ernst, A. Mugler, H.-J. Starkloff, E. Ullmann, On the convergence of generalized polynomial chaos expansions. ESAIM. Math. Model. Numer. Anal. 46(2), 317–339 (2012) MathSciNetMATHCrossRef O.G. Ernst, A. Mugler, H.-J. Starkloff, E. Ullmann, On the convergence of generalized polynomial chaos expansions. ESAIM. Math. Model. Numer. Anal. 46(2), 317–339 (2012) MathSciNetMATHCrossRef
41.
Zurück zum Zitat N. Fajraoui, S. Marelli, B. Sudret, Sequential design of experiment for sparse polynomial chaos expansions. SIAM/ASA J. Uncertain. Quantif. 5(1), 1061–1085 (2017) MathSciNetMATHCrossRef N. Fajraoui, S. Marelli, B. Sudret, Sequential design of experiment for sparse polynomial chaos expansions. SIAM/ASA J. Uncertain. Quantif. 5(1), 1061–1085 (2017) MathSciNetMATHCrossRef
42.
Zurück zum Zitat R. Ghanem, D. Higdon, H. Owhadi, (eds.), Handbook of Uncertainty Quantification (Springer, Switzerland, 2017) MATH R. Ghanem, D. Higdon, H. Owhadi, (eds.), Handbook of Uncertainty Quantification (Springer, Switzerland, 2017) MATH
43.
Zurück zum Zitat L. Guo, Y. Liu, L. Yan, Sparse recovery via ℓ q-minimization for polynomial chaos expansions. Numer. Math. Theor. Meth. Appl. 10(4), 775–797 (2017) MathSciNetMATHCrossRef L. Guo, Y. Liu, L. Yan, Sparse recovery via q-minimization for polynomial chaos expansions. Numer. Math. Theor. Meth. Appl. 10(4), 775–797 (2017) MathSciNetMATHCrossRef
44.
Zurück zum Zitat L. Guo, A. Narayan, T. Zhou, Y. Chen, Stochastic collocation methods via ℓ 1 minimization using randomized quadratures. SIAM J. Sci. Comput. 39(1), A333–A359 (2017) MathSciNetMATHCrossRef L. Guo, A. Narayan, T. Zhou, Y. Chen, Stochastic collocation methods via 1 minimization using randomized quadratures. SIAM J. Sci. Comput. 39(1), A333–A359 (2017) MathSciNetMATHCrossRef
45.
Zurück zum Zitat L. Guo, A. Narayan, T. Zhou, A gradient enhanced ℓ 1-minimization for sparse approximation of polynomial chaos expansions. J. Comput. Phys. 367, 49–64 (2018) MathSciNetMATHCrossRef L. Guo, A. Narayan, T. Zhou, A gradient enhanced 1-minimization for sparse approximation of polynomial chaos expansions. J. Comput. Phys. 367, 49–64 (2018) MathSciNetMATHCrossRef
46.
47.
Zurück zum Zitat C. Haberstich, A. Nouy, and G. Perrin. Boosted optimal weighted least-squares (2019). arXiv:1912.07075 C. Haberstich, A. Nouy, and G. Perrin. Boosted optimal weighted least-squares (2019). arXiv:1912.07075
48.
Zurück zum Zitat M. Hadigol, A. Doostan, Least squares polynomial chaos expansion: a review of sampling strategies. Comput. Methods Appl. Mech. Eng. 332, 382–407 (2018) MathSciNetMATHCrossRef M. Hadigol, A. Doostan, Least squares polynomial chaos expansion: a review of sampling strategies. Comput. Methods Appl. Mech. Eng. 332, 382–407 (2018) MathSciNetMATHCrossRef
49.
Zurück zum Zitat J. Hampton, A. Doostan, Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression. Comput. Methods Appl. Mech. Eng. 290, 73–97 (2015) MathSciNetMATHCrossRef J. Hampton, A. Doostan, Coherence motivated sampling and convergence analysis of least squares polynomial chaos regression. Comput. Methods Appl. Mech. Eng. 290, 73–97 (2015) MathSciNetMATHCrossRef
50.
Zurück zum Zitat J. Hampton, A. Doostan, Compressive sampling of polynomial chaos expansions: Convergence analysis and sampling strategies. J. Comput. Phys. 280, 363–386 (2015) MathSciNetMATHCrossRef J. Hampton, A. Doostan, Compressive sampling of polynomial chaos expansions: Convergence analysis and sampling strategies. J. Comput. Phys. 280, 363–386 (2015) MathSciNetMATHCrossRef
51.
Zurück zum Zitat J. Hampton, A. Doostan, Compressive sampling methods for sparse polynomial chaos expansions, in Handbook of Uncertainty Quantification, ed. by R. Ghanem, D. Higdon, H. Owhadi (Springer, Cham, Switzerland, 2017), pp. 827–855 CrossRef J. Hampton, A. Doostan, Compressive sampling methods for sparse polynomial chaos expansions, in Handbook of Uncertainty Quantification, ed. by R. Ghanem, D. Higdon, H. Owhadi (Springer, Cham, Switzerland, 2017), pp. 827–855 CrossRef
52.
53.
Zurück zum Zitat M. Hansen, C. Schwab, Analytic regularity and nonlinear approximation of a class of parametric semilinear elliptic PDEs. Math. Nachr. 286(8–9), 832–860 (2013) MathSciNetMATHCrossRef M. Hansen, C. Schwab, Analytic regularity and nonlinear approximation of a class of parametric semilinear elliptic PDEs. Math. Nachr. 286(8–9), 832–860 (2013) MathSciNetMATHCrossRef
54.
Zurück zum Zitat A. Hashemi, H. Schaeffer, R. Shi, U. Topcu, G. Tran, R. Ward, Generalization bounds for sparse random feature expansions (2021). arXiv:2103.03191 A. Hashemi, H. Schaeffer, R. Shi, U. Topcu, G. Tran, R. Ward, Generalization bounds for sparse random feature expansions (2021). arXiv:2103.03191
55.
Zurück zum Zitat L.S.T. Ho, H. Schaeffer, G. Tran, R. Ward, Recovery guarantees for polynomial coefficients from weakly dependent data with outliers. J. Approx. Theory 259, 105472 (2020) MathSciNetMATHCrossRef L.S.T. Ho, H. Schaeffer, G. Tran, R. Ward, Recovery guarantees for polynomial coefficients from weakly dependent data with outliers. J. Approx. Theory 259, 105472 (2020) MathSciNetMATHCrossRef
56.
Zurück zum Zitat V.H. Hoang, C. Schwab, Regularity and generalized polynomial chaos approximation of parametric and random second-order hyperbolic partial differential equations. Anal. Appl. (Singap.) 10(3), 295–326 (2012) V.H. Hoang, C. Schwab, Regularity and generalized polynomial chaos approximation of parametric and random second-order hyperbolic partial differential equations. Anal. Appl. (Singap.) 10(3), 295–326 (2012)
57.
Zurück zum Zitat J.D. Jakeman, M.S. Eldred, K. Sargsyan, Enhancing ℓ 1-minimization estimates of polynomial chaos expansions using basis selection. J. Comput. Phys. 289, 18–34 (2015) MathSciNetMATHCrossRef J.D. Jakeman, M.S. Eldred, K. Sargsyan, Enhancing 1-minimization estimates of polynomial chaos expansions using basis selection. J. Comput. Phys. 289, 18–34 (2015) MathSciNetMATHCrossRef
58.
Zurück zum Zitat J.D. Jakeman, A. Narayan, T. Zhou, A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions. SIAM J. Sci. Comput. 39(3), A1114–A1144 (2017) MathSciNetMATHCrossRef J.D. Jakeman, A. Narayan, T. Zhou, A generalized sampling and preconditioning scheme for sparse approximation of polynomial chaos expansions. SIAM J. Sci. Comput. 39(3), A1114–A1144 (2017) MathSciNetMATHCrossRef
59.
Zurück zum Zitat J.D. Jakeman, F. Franzelin, A. Narayan, M. Eldred, D. Plüger, Polynomial chaos expansions for dependent random variables. Comput. Methods Appl. Mech. Eng. 351, 643–666 (2019) MathSciNetMATHCrossRef J.D. Jakeman, F. Franzelin, A. Narayan, M. Eldred, D. Plüger, Polynomial chaos expansions for dependent random variables. Comput. Methods Appl. Mech. Eng. 351, 643–666 (2019) MathSciNetMATHCrossRef
60.
Zurück zum Zitat I.A. Kougioumtzoglou, I. Petromichelakis, A.F. Psaros, Sparse representations and compressive sampling approaches in engineering mechanics: A review of theoretical concepts and diverse applications. Probabilistic Eng. Mech. 61, 103082 (2020) CrossRef I.A. Kougioumtzoglou, I. Petromichelakis, A.F. Psaros, Sparse representations and compressive sampling approaches in engineering mechanics: A review of theoretical concepts and diverse applications. Probabilistic Eng. Mech. 61, 103082 (2020) CrossRef
61.
Zurück zum Zitat O. Le Maître, O.M. Knio, Spectral Methods for Uncertainty Quantification: With Applications to Computational Fluid Dynamics. Sci. Comput. (Springer, Dordrecht, Netherlands, 2010) O. Le Maître, O.M. Knio, Spectral Methods for Uncertainty Quantification: With Applications to Computational Fluid Dynamics. Sci. Comput. (Springer, Dordrecht, Netherlands, 2010)
62.
Zurück zum Zitat Y. Liu, L. Guo, Stochastic collocation via l 1-minimisation on low discrepancy point sets with application to uncertainty quantification. East Asian J. Appl. Math. 6(2), 171–191 (2016) MathSciNetMATHCrossRef Y. Liu, L. Guo, Stochastic collocation via l 1-minimisation on low discrepancy point sets with application to uncertainty quantification. East Asian J. Appl. Math. 6(2), 171–191 (2016) MathSciNetMATHCrossRef
63.
Zurück zum Zitat N. Lüthen, S. Marelli, B. Sudret, Automatic selection of basis-adaptive sparse polynomial chaos expansions for engineering applications (2021). arXiv:2009.04800 N. Lüthen, S. Marelli, B. Sudret, Automatic selection of basis-adaptive sparse polynomial chaos expansions for engineering applications (2021). arXiv:2009.04800
64.
Zurück zum Zitat N. Lüthen, S. Marelli, B. Sudret, Sparse polynomial chaos expansions: Literature survey and benchmark. SIAM/ASA J. Uncertain. Quantif. 9(2), 593–649 (2021) MathSciNetMATHCrossRef N. Lüthen, S. Marelli, B. Sudret, Sparse polynomial chaos expansions: Literature survey and benchmark. SIAM/ASA J. Uncertain. Quantif. 9(2), 593–649 (2021) MathSciNetMATHCrossRef
65.
Zurück zum Zitat L. Mathelin, K.A. Gallivan, A compressed sensing approach for partial differential equations with random input data. Commun. Comput. Phys. 12(4), 919–954 (2012) MathSciNetMATHCrossRef L. Mathelin, K.A. Gallivan, A compressed sensing approach for partial differential equations with random input data. Commun. Comput. Phys. 12(4), 919–954 (2012) MathSciNetMATHCrossRef
66.
Zurück zum Zitat G. Migliorati, Polynomial approximation by means of the random discrete L 2 projection and application to inverse problems for PDEs with stochastic data, PhD thesis, Politecnico di Milano, 2013 G. Migliorati, Polynomial approximation by means of the random discrete L 2 projection and application to inverse problems for PDEs with stochastic data, PhD thesis, Politecnico di Milano, 2013
67.
Zurück zum Zitat G. Migliorati, Adaptive approximation by optimal weighted least squares methods. SIAM J. Numer. Anal. 57(5), 2217–2245 (2019) MathSciNetMATHCrossRef G. Migliorati, Adaptive approximation by optimal weighted least squares methods. SIAM J. Numer. Anal. 57(5), 2217–2245 (2019) MathSciNetMATHCrossRef
68.
Zurück zum Zitat G. Migliorati, Multivariate approximation of functions on irregular domains by weighted least-squares methods. IMA J. Numer. Anal. 41(2), 1293–1317 (2021) MathSciNetMATHCrossRef G. Migliorati, Multivariate approximation of functions on irregular domains by weighted least-squares methods. IMA J. Numer. Anal. 41(2), 1293–1317 (2021) MathSciNetMATHCrossRef
69.
Zurück zum Zitat G. Migliorati, F. Nobile, Analysis of discrete least squares on multivariate polynomial spaces with evaluations in low-discrepancy point sets. J. Complexity 31, 517–542 (2015) MathSciNetMATHCrossRef G. Migliorati, F. Nobile, Analysis of discrete least squares on multivariate polynomial spaces with evaluations in low-discrepancy point sets. J. Complexity 31, 517–542 (2015) MathSciNetMATHCrossRef
70.
Zurück zum Zitat G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Analysis of the discrete L 2 projection on polynomial spaces with random evaluations. Found. Comput. Math. 14, 419–456 (2014) MathSciNetMATH G. Migliorati, F. Nobile, E. von Schwerin, R. Tempone, Analysis of the discrete L 2 projection on polynomial spaces with random evaluations. Found. Comput. Math. 14, 419–456 (2014) MathSciNetMATH
71.
72.
73.
Zurück zum Zitat A. Narayan, J.D. Jakeman, T. Zhou, A Christoffel function weighted least squares algorithm for collocation approximations. Math. Comput. 86, 1913–1947 (2017) MathSciNetMATHCrossRef A. Narayan, J.D. Jakeman, T. Zhou, A Christoffel function weighted least squares algorithm for collocation approximations. Math. Comput. 86, 1913–1947 (2017) MathSciNetMATHCrossRef
74.
Zurück zum Zitat L.W.-T. Ng, M. Eldred, Multifidelity uncertainty quantification using nonintrusive polynomial chaos and stochastic collocation, in 53rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, vol. 45 (AIAA, 2012) L.W.-T. Ng, M. Eldred, Multifidelity uncertainty quantification using nonintrusive polynomial chaos and stochastic collocation, in 53rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference, vol. 45 (AIAA, 2012)
75.
Zurück zum Zitat J. Peng, J. Hampton, A. Doostan, A weighted ℓ 1-minimization approach for sparse polynomial chaos expansions. J. Comput. Phys. 267, 92–111 (2014) MathSciNetMATHCrossRef J. Peng, J. Hampton, A. Doostan, A weighted 1-minimization approach for sparse polynomial chaos expansions. J. Comput. Phys. 267, 92–111 (2014) MathSciNetMATHCrossRef
76.
Zurück zum Zitat J. Peng, J. Hampton, A. Doostan, On polynomial chaos expansion via gradient-enhanced l 1-minimization. J. Comput. Phys. 310, 440–458 (2016) MathSciNetMATHCrossRef J. Peng, J. Hampton, A. Doostan, On polynomial chaos expansion via gradient-enhanced l 1-minimization. J. Comput. Phys. 310, 440–458 (2016) MathSciNetMATHCrossRef
77.
Zurück zum Zitat G. Plonka, D. Potts, G. Steidl, M. Tasche, Numerical Fourier Analysis. Appl. Numer. Harmon. Anal. (Birkhäuser, Cham, Switzerland, 2018) G. Plonka, D. Potts, G. Steidl, M. Tasche, Numerical Fourier Analysis. Appl. Numer. Harmon. Anal. (Birkhäuser, Cham, Switzerland, 2018)
78.
Zurück zum Zitat H. Rauhut, C. Schwab, Compressive sensing Petrov-Galerkin approximation of high dimensional parametric operator equations. Math. Comput. 86, 661–700 (2017) MathSciNetMATHCrossRef H. Rauhut, C. Schwab, Compressive sensing Petrov-Galerkin approximation of high dimensional parametric operator equations. Math. Comput. 86, 661–700 (2017) MathSciNetMATHCrossRef
79.
80.
81.
Zurück zum Zitat Y. Shin, D. Xiu, Correcting data corruption errors for multivariate function approximation. SIAM J. Sci. Comput. 38(4), A2492–A2511 (2016) MathSciNetMATHCrossRef Y. Shin, D. Xiu, Correcting data corruption errors for multivariate function approximation. SIAM J. Sci. Comput. 38(4), A2492–A2511 (2016) MathSciNetMATHCrossRef
82.
Zurück zum Zitat Y. Shin, D. Xiu, Nonadaptive quasi-optimal points selection for least squares linear regression. SIAM J. Sci. Comput. 38(1), A385–A411 (2016) MathSciNetMATHCrossRef Y. Shin, D. Xiu, Nonadaptive quasi-optimal points selection for least squares linear regression. SIAM J. Sci. Comput. 38(1), A385–A411 (2016) MathSciNetMATHCrossRef
83.
Zurück zum Zitat R.C. Smith, Uncertainty Quantification: Theory, Implementation, and Applications (Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2013) R.C. Smith, Uncertainty Quantification: Theory, Implementation, and Applications (Comput. Sci. Eng. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2013)
84.
Zurück zum Zitat C. Soize, R. Ghanem, Physical systems with random uncertainties: Chaos representations with arbitrary probability measure. SIAM J. Sci. Comput. 26(2), 395–410 (2004) MathSciNetMATHCrossRef C. Soize, R. Ghanem, Physical systems with random uncertainties: Chaos representations with arbitrary probability measure. SIAM J. Sci. Comput. 26(2), 395–410 (2004) MathSciNetMATHCrossRef
85.
Zurück zum Zitat T.J. Sullivan, Introduction to Uncertainty Quantification, vol. 63 of Texts Appl. Math. (Springer, Cham, Switzerland, 2015) T.J. Sullivan, Introduction to Uncertainty Quantification, vol. 63 of Texts Appl. Math. (Springer, Cham, Switzerland, 2015)
86.
Zurück zum Zitat G. Tang, Methods for high dimensional uncertainty quantification: regularization, sensitivity analysis, and derivative enhancement, PhD thesis, Stanford University, 2013 G. Tang, Methods for high dimensional uncertainty quantification: regularization, sensitivity analysis, and derivative enhancement, PhD thesis, Stanford University, 2013
87.
Zurück zum Zitat G. Tang, G. Iaccarino, Subsampled Gauss quadrature nodes for estimating polynomial chaos expansions. SIAM/ASA J. Uncertain. Quantif. 2(1), 423–443 (2014) MathSciNetMATHCrossRef G. Tang, G. Iaccarino, Subsampled Gauss quadrature nodes for estimating polynomial chaos expansions. SIAM/ASA J. Uncertain. Quantif. 2(1), 423–443 (2014) MathSciNetMATHCrossRef
88.
Zurück zum Zitat T. Tang, T. Zhou, On discrete least-squares projection in unbounded domain with random evaluations and its application to parametric uncertainty quantification. SIAM J. Sci. Comput. 36(5), A2272–A2295 (2014) MathSciNetMATHCrossRef T. Tang, T. Zhou, On discrete least-squares projection in unbounded domain with random evaluations and its application to parametric uncertainty quantification. SIAM J. Sci. Comput. 36(5), A2272–A2295 (2014) MathSciNetMATHCrossRef
89.
Zurück zum Zitat V. Temlyakov, Multivariate Approximation, vol. 32 (Cambridge University Press, 2018) V. Temlyakov, Multivariate Approximation, vol. 32 (Cambridge University Press, 2018)
90.
Zurück zum Zitat H. Tran, C. Webster, Analysis of sparse recovery for Legendre expansions using envelope bound (2018). arXiv:1810.02926 H. Tran, C. Webster, Analysis of sparse recovery for Legendre expansions using envelope bound (2018). arXiv:1810.02926
91.
Zurück zum Zitat H. Tran, C. Webster, A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations. Results Appl. Math. 3, 100011 (2019) MathSciNetMATHCrossRef H. Tran, C. Webster, A class of null space conditions for sparse recovery via nonconvex, non-separable minimizations. Results Appl. Math. 3, 100011 (2019) MathSciNetMATHCrossRef
92.
Zurück zum Zitat H. Tran, C.G. Webster, G. Zhang, Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients. Numer. Math. 137(2), 451–493 (2017) MathSciNetMATHCrossRef H. Tran, C.G. Webster, G. Zhang, Analysis of quasi-optimal polynomial approximations for parameterized PDEs with deterministic and stochastic coefficients. Numer. Math. 137(2), 451–493 (2017) MathSciNetMATHCrossRef
94.
Zurück zum Zitat P. Tsilifis, X. Huan, C. Safta, K. Sargsyan, G. Lacaze, J.C. Oefelein, H.N. Najm, R.G. Ghanem, Compressive sensing adaptation for polynomial chaos expansions. J. Comput. Phys. 380, 29–47 (2019) MathSciNetMATHCrossRef P. Tsilifis, X. Huan, C. Safta, K. Sargsyan, G. Lacaze, J.C. Oefelein, H.N. Najm, R.G. Ghanem, Compressive sensing adaptation for polynomial chaos expansions. J. Comput. Phys. 380, 29–47 (2019) MathSciNetMATHCrossRef
95.
Zurück zum Zitat Z. Xu, T. Zhou, On sparse interpolation and the design of deterministic interpolation points. SIAM J. Sci. Comput. 36(4), 1752–1769 (2014) MathSciNetMATHCrossRef Z. Xu, T. Zhou, On sparse interpolation and the design of deterministic interpolation points. SIAM J. Sci. Comput. 36(4), 1752–1769 (2014) MathSciNetMATHCrossRef
96.
Zurück zum Zitat Y. Xu, A. Narayan, H. Tran, C. Webster, Analysis of the ratio of ℓ 1 and ℓ 2 norms in compressed sensing (2020). arXiv:2004.05873 Y. Xu, A. Narayan, H. Tran, C. Webster, Analysis of the ratio of 1 and 2 norms in compressed sensing (2020). arXiv:2004.05873
97.
Zurück zum Zitat L. Yan, L. Guo, D. Xiu, Stochastic collocation algorithms using ℓ 1-minimization. Int. J. Uncertain. Quantif. 2(3), 279–293 (2012) MathSciNetMATHCrossRef L. Yan, L. Guo, D. Xiu, Stochastic collocation algorithms using 1-minimization. Int. J. Uncertain. Quantif. 2(3), 279–293 (2012) MathSciNetMATHCrossRef
98.
Zurück zum Zitat L. Yan, Y. Shin, D. Xiu, Sparse approximation using ℓ 1 −  ℓ 2 minimization and its application to stochastic collocation. SIAM J. Sci. Comput. 39(1), A229–A254 (2017) MathSciNetMATHCrossRef L. Yan, Y. Shin, D. Xiu, Sparse approximation using 1 −  2 minimization and its application to stochastic collocation. SIAM J. Sci. Comput. 39(1), A229–A254 (2017) MathSciNetMATHCrossRef
99.
Zurück zum Zitat X. Yang, G.E. Karniadakis, Reweighted ℓ 1 minimization method for stochastic elliptic differential equations. J. Comput. Phys. 248, 87–108 (2013) MATHCrossRef X. Yang, G.E. Karniadakis, Reweighted 1 minimization method for stochastic elliptic differential equations. J. Comput. Phys. 248, 87–108 (2013) MATHCrossRef
100.
Zurück zum Zitat X. Yang, H. Lei, N.A. Baker, G. Lin, Enhancing sparsity of Hermite polynomial expansions by iterative rotations. J. Comput. Phys. 307, 94–109 (2016) MathSciNetMATHCrossRef X. Yang, H. Lei, N.A. Baker, G. Lin, Enhancing sparsity of Hermite polynomial expansions by iterative rotations. J. Comput. Phys. 307, 94–109 (2016) MathSciNetMATHCrossRef
101.
Zurück zum Zitat X. Yang, W. Li, A. Tartakovsky, Sliced-inverse-regression–aided rotated compressive sensing method for uncertainty quantification. SIAM/ASA J. Uncertain. Quantif. 6(4), 1532–1554 (2018) MathSciNetMATHCrossRef X. Yang, W. Li, A. Tartakovsky, Sliced-inverse-regression–aided rotated compressive sensing method for uncertainty quantification. SIAM/ASA J. Uncertain. Quantif. 6(4), 1532–1554 (2018) MathSciNetMATHCrossRef
102.
Zurück zum Zitat X. Yang, X. Wan, L. Lin, H. Lei, A general framework for enhancing sparsity of generalized polynomial chaos expansions. Int. J. Uncertain. Quantif. 9(3), 221–243 (2019) MathSciNetCrossRef X. Yang, X. Wan, L. Lin, H. Lei, A general framework for enhancing sparsity of generalized polynomial chaos expansions. Int. J. Uncertain. Quantif. 9(3), 221–243 (2019) MathSciNetCrossRef
103.
Zurück zum Zitat S. Zein, B. Colson, F. Glineur, An efficient sampling method for regression-based polynomial chaos expansion. Commun. Comput. Phys. 13(4), 1173–1188 (2013) MathSciNetMATHCrossRef S. Zein, B. Colson, F. Glineur, An efficient sampling method for regression-based polynomial chaos expansion. Commun. Comput. Phys. 13(4), 1173–1188 (2013) MathSciNetMATHCrossRef
104.
Zurück zum Zitat T. Zhou, A. Narayan, Z. Xu, Multivariate discrete least-squares approximations with a new type of collocation grid. SIAM J. Sci. Comput. 36(5), A2401–A2422 (2014) MathSciNetMATHCrossRef T. Zhou, A. Narayan, Z. Xu, Multivariate discrete least-squares approximations with a new type of collocation grid. SIAM J. Sci. Comput. 36(5), A2401–A2422 (2014) MathSciNetMATHCrossRef
105.
Zurück zum Zitat T. Zhou, A. Narayan, D. Xiu, Weighted discrete least-squares polynomial approximation using randomized quadratures. J. Comput. Phys. 298, 787–800 (2015) MathSciNetMATHCrossRef T. Zhou, A. Narayan, D. Xiu, Weighted discrete least-squares polynomial approximation using randomized quadratures. J. Comput. Phys. 298, 787–800 (2015) MathSciNetMATHCrossRef
Metadaten
Titel
Towards Optimal Sampling for Learning Sparse Approximations in High Dimensions
verfasst von
Ben Adcock
Juan M. Cardenas
Nick Dexter
Sebastian Moraga
Copyright-Jahr
2022
DOI
https://doi.org/10.1007/978-3-031-00832-0_2

Stellenausschreibungen

Anzeige

Premium Partner