Data Entry: Please note that the research database will be replaced by UNIverse by the end of October 2023. Please enter your data into the system https://universe-intern.unibas.ch. Thanks
Approximation of bi-variate functions : singular value decomposition versus sparse grids
Journal
IMA journal of numerical analysis
Volume
34
Number
1
Pages / Article-Number
28-54
Keywords
singular value decomposition, sparse grids, complexity
Abstract
We compare the cost complexities of two approximation schemes for functions $f\in H^p(\Omega_1\times \Omega_2)$ which live on the product domain $\Omega_1\times\Omega_2$ of sufficiently smooth domains $\Omega_1\subset\mathbb{R}^{n_1}$ and $\Omega_2\subset\mathbb{R}^{n_2}$, namely the singular value / Karhunen-L\`oeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated {\em fixed} order $r$ of accuracy are given on the domains $\Omega_1$ and $\Omega_2$. Then, the sparse grid approximation essentially needs only $\mathcal{O}(\varepsilon^{-q})$ with $q=\frac{\max\{n_1,n_2\}}{r}$ unknowns to reach a prescribed accuracy $\varepsilon$ provided that the smoothness of $f$ satisfies $p\ge r\frac{n_1+n_2}{\max\{n_1,n_2\}}$, which is an almost optimal rate. The singular value decomposition produces this rate only if $f$ is analytical since otherwise the decay of the singular values is not fast enough. If $p<r\frac{n_1+n_2}{\max\{n_1,n_2\}}$, then the sparse grid approach gives essentially the rate $\mathcal{O}(\varepsilon^{-q})$ with $q=\frac{n_1+n_2}{p}$ while, for the singular value decomposition, we can only prove the rate $\mathcal{O}(\varepsilon^{-q})$ with $q=\frac{2\min\{r,p\}\min\{n_1,n_2\}+2p\max\{n_1,n_2\}}{(2p-\min\{n_1,n_2\})\min\{r,p\}}$. We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practice.
$p
\frac{n_1+n_2}{\max\{n_1,n_2\}}$, then the sparse
grid approach gives essentially the rate $\mathcal{O}
(\varepsilon^{-q})$ with $q=\frac{n_1+n_2}{p}$ while, for the
singular value decomposition, we can only prove the rate
$\mathcal{O}(\varepsilon^{-q})$ with $q=\frac{2\min\{r,p\}\min\{n_1,n_2\}