Dinh Dũng

Dinh Dũng, Vladimir N. Temlyakov, Tino Ullrich

Hyperbolic cross approximation is a special type of multivariate approximation. Recently, driven by applications in engineering, biology, medicine and other areas of science new challenging problems have appeared. The common feature of these problems is high dimensions. We present here a survey on classical methods developed in multivariate approximation theory, which are known to work very well for moderate dimensions and which have potential for applications in really high dimensions. The theory of hyperbolic cross approximation and related theory of functions with mixed smoothness are under detailed study for more than 50 years. It is now well understood that this theory is important both for theoretical study and for practical applications. It is also understood that both theoretical analysis and construction of practical algorithms are very difficult problems. This explains why many fundamental problems in this area are still unsolved. Only a few survey papers and monographs on the topic are published. This and recently discovered deep connections between the hyperbolic cross approximation (and related sparse grids) and other areas of mathematics such as probability, discrepancy, and numerical integration motivated us to write this survey. We try to put emphases on the development of ideas and methods rather than list all the known results in the area. We formulate many problems, which, to our knowledge, are open problems. We also include some very recent results on the topic, which sometimes highlight new interesting directions of research. We hope that this survey will stimulate further active research in this fascinating and challenging area of approximation theory and numerical analysis.

Dinh Dũng, Michael Griebel

We give tight upper and lower bounds of the cardinality of the index sets of certain hyperbolic crosses which reflect mixed Sobolev-Korobov-type smoothness and mixed Sobolev-analytic-type smoothness in the infinite-dimensional case where specific summability properties of the smoothness indices are fulfilled. These estimates are then applied to the linear approximation of functions from the associated spaces in terms of the $\varepsilon$-dimension of their unit balls. Here, the approximation is based on linear information. Such function spaces appear for example for the solution of parametric and stochastic PDEs. The obtained upper and lower bounds of the approximation error as well as of the associated $\varepsilon$-complexities are completely independent of any dimension. Moreover, the rates are independent of the parameters which define the smoothness properties of the infinite-variate parametric or stochastic part of the solution. These parameters are only contained in the order constants. This way, linear approximation theory becomes possible in the infinite-dimensional case and corresponding infinite-dimensional problems get tractable.

Glenn Byrenheid, Dinh Dũng, Winfried Sickel et al.

We investigate the rate of convergence of linear sampling numbers of the embedding $H^{α,β} (\mathbb{T}^d) \hookrightarrow H^γ(\mathbb{T}^d)$. Here $α$ governs the mixed smoothness and $β$ the isotropic smoothness in the space $H^{α,β}(\mathbb{T}^d)$ of hybrid smoothness, whereas $H^γ(\mathbb{T}^d)$ denotes the isotropic Sobolev space. If $γ>β$ we obtain sharp polynomial decay rates for the first embedding realized by sampling operators based on "energy-norm based sparse grids" for the classical trigonometric interpolation. This complements earlier work by Griebel, Knapek and Dũng, Ullrich, where general linear approximations have been considered. In addition, we study the embedding $H^α_{mix} (\mathbb{T}^d) \hookrightarrow H^γ_{mix}(\mathbb{T}^d)$ and achieve optimality for Smolyak's algorithm applied to the classical trigonometric interpolation. This can be applied to investigate the sampling numbers for the embedding $H^α_{mix} (\mathbb{T}^d) \hookrightarrow L_q(\mathbb{T}^d)$ for $2<q\leq \infty$ where again Smolyak's algorithm yields the optimal order. The precise decay rates for the sampling numbers in the mentioned situations always coincide with those for the approximation numbers, except probably in the limiting situation $β= γ$ (including the embedding into $L_2(\mathbb{T}^d)$). The best what we could prove there is a (probably) non-sharp results with a logarithmic gap between lower and upper bound.

Dinh Dũng, Michael Griebel, Vu Nhat Huy et al.

In this article, we present a cost-benefit analysis of the approximation in tensor products of Hilbert spaces of Sobolev-analytic type. The Sobolev part is defined on a finite dimensional domain, whereas the analytical space is defined on an infinite dimensional domain. As main mathematical tool, we use the $\varepsilon$-dimension of a subset in a Hilbert space. The $\varepsilon$-dimension gives the lowest number of linear information that is needed to approximate an element from the set in the norm of the Hilbert space up to an accuracy $\varepsilon>0$. From a practical point of view this means that we a priori fix an accuracy and ask for the amount of information to achieve this accuracy. Such an analysis usually requires sharp estimates on the cardinality of certain index sets which are in our case infinite-dimensional hyperbolic crosses. As main result, we obtain sharp bounds of the $\varepsilon$-dimension of the Sobolev-analytic-type function classes which depend only on the smoothness differences in the Sobolev spaces and the dimension of the finite dimensional domain where these spaces are defined. This implies in particular that, up to constants, the costs of the infinite dimensional (analytical) approximation problem is dominated by the finite-variate Sobolev approximation problem. We demonstrate this procedure with an examples of functions spaces stemming from the regularity theory of parametric partial differential equation.

Dinh Dũng, Charles A. Micchelli, Vu Nhat Huy

We study approximation by arbitrary linear combinations of $n$ translates of a single function of periodic functions. We construct some methods of this approximation for functions in a class induced by the convolution with a given function, and prove upper bounds of $L_p$-the approximation convergence rate by these methods, when $n \to \infty$, for $1 < p < \infty$, and lower bounds of the quantity of best approximation of this class by arbitrary linear combinations of $n$ translates of arbitrary function, for the particular case $p=2$.

Dinh Dũng

Let $X_n = \{x^j\}_{j=1}^n$ be a set of $n$ points in the $d$-cube $[0,1]^d$, and $Φ_n = \{φ_j\}_{j =1}^n$ a family of $n$ functions on $[0,1]^d$. We consider the approximate recovery functions $f$ on $[0,1]^d$ from the sampled values $f(x^1), ..., f(x^n)$, by the linear sampling algorithm \begin{equation} \nonumber L_n(X_n,Φ_n,f) \ := \ \sum_{j=1}^n f(x^j)φ_j. \end{equation} The error of sampling recovery is measured in the norm of the space $L_q([0,1]^d)$-norm or the energy norm of the isotropic Sobolev sapce $W^γ_q([0,1]^d)$ for $0 < q \le \infty$ and $γ> 0$. Functions $f$ to be recovered are from the unit ball in Besov type spaces of an anisotropic smoothness, in particular, spaces $B^a_{p,θ}$ of a nonuniform mixed smoothness $a \in {\mathbb R}^d_+$, and spaces $B^{α,β}_{p,θ}$ of a "hybrid" of mixed smoothness $α> 0$ and isotropic smoothness $β\in \mathbb R$. We constructed optimal linear sampling algorithms $L_n(X_n^*,Φ_n^*,\cdot)$ on special sparse grids $X_n^*$ and a family $Φ_n^*$ of linear combinations of integer or half integer translated dilations of tensor products of B-splines. We computed the asymptotic of the error of the optimal recovery. This construction is based on a B-spline quasi-interpolation representations of functions in $B^a_{p,θ}$ and $B^{α,β}_{p,θ}$. As consequences we obtained the asymptotic of optimal cubature formulas for numerical integration of functions from the unit ball of these Besov type spaces.

Dinh Dũng

We proved direct and inverse theorems on B-spline quasi-interpolation sampling representation with a Littlewood-Paley-type norm equivalence in Sobolev spaces $W^r_p$ of mixed smoothness $r$, established estimates of the approximation error of recovery in $L_q$-norm of functions from the unit ball $U^r_p$ in the spaces $W^r_p$ by linear sampling algorithms based on this representation, the asymptotic optimality of these sampling algorithms in terms of Smolyak sampling width $r^s_n(U^r_p, L_q)$ and sampling width $r_n(U^r_p, L_q)$.

Dinh Dũng

Consider the parametric elliptic problem \begin{equation} - \operatorname{dv} \big(a(y)(x)\nabla u(y)(x)\big) \ = \ f(x) \quad x \in D, \ y \in [-1,1]^\infty, \quad u|_{\partial D} \ = \ 0, \end{equation} where $D \subset {\mathbb R}^m$ is a bounded Lipschitz domain, $[-1,1]^\infty$, $f \in L_2(D)$, and the diffusions $a$ satisfy the uniform ellipticity assumption and are affinely dependent with respect to $y$. The parametric variable $y$ may be deterministic or random. In the present paper, a central question to be studied is as follows. Assume that we have an approximation property that there is a sequence of finite element approximations with a certain error convergence rate in energy norm of the space $V:=H^1_0(D)$ for the nonparametric problem $- \operatorname{dv} \big(a(y_0)(x)\nabla u(y_0)(x)\big) = f(x)$ at every point $y_0 \in [-1,1]^\infty$. Then under what assumptions does this sequence induce a sequence of finite element approximations with the same error convergence rate for the parametric elliptic problem in the norm of the Bochner spaces $L_\infty([-1,1]^\infty,V)$ or $L_2([-1,1]^\infty,V)$? We solved this question by linear collective Taylor, collocation and Galerkin methods, based on Taylor expansions, Lagrange polynomial interpolations and Legendre polynomials expansions, respectively, on the parametric domain $[-1,1]^\infty$. Under very light conditions, we show that all these approximation methods give the same error convergence rate as that by the sequence of finite element approximations for the nonparametric elliptic problem. The parametric infinite-variate part completely disappears from the convergence rate and influences only the constant. Hence the curse of dimensionality is broken by linear methods.

Dinh Dũng

We constructed linear algorithms of sampling recovery and cubature formulas on Smolyak grids parametrized by $m \in \mathbb{N}$ of periodic $d$-variate functions having Lipschitz-Hölder mixed smoothness $α> 0$ based on B-spline quasi-interpolation, and studied their optimality. We established lower estimates (for $α\le 2$) and upper bounds of the error of the optimal sampling recovery and the optimal integration on Smolyak grids, explicit in $d$, $m$ and the number $ν$ of active variables of functions when $d$ and $m$ may be large.

Markus Bachmayr, Albert Cohen, Dinh Dũng et al.

It has recently been demonstrated that locality of spatial supports in the parametrization of coefficients in elliptic PDEs can lead to improved convergence rates of sparse polynomial expansions of the corresponding parameter-dependent solutions. These results by themselves do not yield practically realizable approximations, since they do not cover the approximation of the arising expansion coefficients, which are functions of the spatial variable. In this work, we study the combined spatial and parametric approximability for elliptic PDEs with affine or lognormal parametrizations of the diffusion coefficients and corresponding Taylor, Jacobi, and Hermite expansions, to obtain fully discrete approximations. Our analysis yields convergence rates of the fully discrete approximation in terms of the total number of degrees of freedom. The main vehicle consists in $\ell^p$ summability results for the coefficient sequences measured in higher-order Hilbertian Sobolev norms. We also discuss similar results for non-Hilbertian Sobolev norms which arise naturally when using adaptive spatial discretizations.