Reduced Basis Greedy Selection Using Random Training Sets

Cohen, Albert; Dahmen, Wolfgang; DeVore, Ronald; Nichols, James

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 54 (2020) no. 5, pp. 1509-1524.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

Reduced bases have been introduced for the approximation of parametrized PDEs in applications where many online queries are required. Their numerical efficiency for such problems has been theoretically confirmed in Binev et al. (SIAM J. Math. Anal. 43 (2011) 1457–1472) and DeVore et al. (Constructive Approximation 37 (2013) 455–466), where it is shown that the reduced basis space V$$ of dimension n, constructed by a certain greedy strategy, has approximation error similar to that of the optimal space associated to the Kolmogorov n-width of the solution manifold. The greedy construction of the reduced basis space is performed in an offline stage which requires at each step a maximization of the current error over the parameter space. For the purpose of numerical computation, this maximization is performed over a finite training set obtained through a discretization of the parameter domain. To guarantee a final approximation error ε for the space generated by the greedy algorithm requires in principle that the snapshots associated to this training set constitute an approximation net for the solution manifold with accuracy of order ε. Hence, the size of the training set is the ε covering number for M and this covering number typically behaves like exp(Cε^−1/s) for some C > 0 when the solution manifold has n-width decay O(n^−s). Thus, the shear size of the training set prohibits implementation of the algorithm when ε is small. The main result of this paper shows that, if one is willing to accept results which hold with high probability, rather than with certainty, then for a large class of relevant problems one may replace the fine discretization by a random training set of size polynomial in ε⁻¹. Our proof of this fact is established by using inverse inequalities for polynomials in high dimensions.

Classification : 62M45, 65D05, 68Q32, 65Y20, 68Q30, 35B30, 41A10, 41A25, 58D15, 65C99
Mots-clés : Reduced bases, performance bounds, random sampling, entropy numbers, Kolmogorov $$-widths, sparse high-dimensional polynomial approximation

M. Bachmayr, A. Cohen and G. Migliorati, Sparse polynomial approximation of parametric elliptic PDEs. Part I: affine coefficients. ESAIM: M2AN 51 (2017) 321–339. | DOI | Numdam | MR | Zbl

P. Binev, A. Cohen, W. Dahmen, R. Devore, G. Petrova and P. Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods. SIAM J. Math. Anal. 43 (2011) 1457–1472. | DOI | MR | Zbl

A. Buffa, Y. Maday, A.T. Patera, C. Prud’Homme, G. Turinici, A priori convergence of the Greedy algorithm for the parameterized reduced basis. ESAIM: M2AN 46 (2012) 595–603. | DOI | Numdam | MR | Zbl

A. Chkifa, A. Cohen, G. Migliorati, F. Nobile and R. Tempone, Discrete least squares polynomial approximation with random evaluations – application to parametric and stochastic elliptic PDEs. ESAIM: M2AN 49 (2015) 815–837. | DOI | Numdam | MR | Zbl

A. Chkifa, A. Cohen and C. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric PDEs. J. Math. Pures Appl. 103 (2015) 400–428. | DOI | MR | Zbl

A. Cohen and R. Devore, Approximation of high-dimensional PDEs. Acta Numer. 24 (2015) 1–159. | DOI | MR | Zbl

A. Cohen, R. Devore and C. Schwab, Analytic regularity and polynomial approximation of parametric and stochastic PDEs. Anal. Appl. 9 (2011) 11–47. | DOI | MR | Zbl

A. Cohen and G. Migliorati, Multivariate approximation in downward closed polynomial spaces. In: Contemporary Computational Mathematics – A Celebration of the 80th Birthday of Ian Sloan. Springer, Cham (2018) 233–282. | DOI | MR | Zbl

R. Devore, G. Petrova and P. Wojtaszczyk, Greedy algorithms for reduced bases in Banach spaces. Constr. Approx. 37 (2013) 455–466. | DOI | MR | Zbl

Y. Maday, A.T. Patera and G. Turinici, A priori convergence theory for reduced-basis approximations of single-parametric elliptic partial differential equations. J. Sci. Comput. 17 (2002) 437–446. | DOI | MR | Zbl

Y. Maday, A.T. Patera and G. Turinici, Global a priori convergence theory for reduced-basis approximations of single-parameter symmetric coercive elliptic partial differential equations. C. R. Acad. Sci. Paris Sér. I Math. 335 (2002) 289–294. | DOI | MR | Zbl

A.T. Patera, C. Prudõhomme, D.V. Rovas and K. Veroy, A posteriori error bounds for reduced-basis approximation of parametrized noncoercive and nonlinear elliptic partial differential equations, In: Proc. 16th AIAA Computational Fluid Dynamics Conference (2003).

G. Pisier, The Volume of Convex Bodies and Banach Spaces Geometry. Cambridge University Press (1989). | DOI | MR | Zbl

G. Rozza, D.B.P. Huynh and A.T. Patera, Reduced basis approximation and a posteriori error estimation for affinely parametrized elliptic coercive partial differential equations application to transport and continuum mechanics. Arch. Comput. Methods Eng. 15 (2008) 229–275. | DOI | MR | Zbl

S. Sen, Reduced-basis approximation and a posteriori error estimation for many-parameter heat conduction problems. Numer. Heat Transfer B-Fund 54 (2008) 369–389. | DOI

V.N. Temlyakov, The Marcinkiewicz-type discretization theorems. Constr. Approx. 48 (2018) 337–369. | DOI | MR | Zbl