Singular value decomposition versus sparse grids: Refined complexity estimates

Abstract

We compare the cost complexities of two approximation schemes for functions which live on the product domain <em>Ω₁</em> × <em>Ω₂</em> of sufficiently smooth domains <em>Ω₁</em> ⊂ <em>R^n₁</em> and <em>Ω₂</em> ⊂ <em>R^n₂</em> , namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. We assume that appropriate finite element methods with associated orders <em>r₁</em> and <em>r₂</em> of accuracy are given on the domains <em>Ω₁</em> and <em>Ω₂</em>, respectively. This setting reflects practical needs, since often black-box solvers are used in numerical simulation which restrict the freedom in the choice of the underlying discretization. We compare the cost complexities of the associated singular value decomposition and the associated sparse grid approximation. It turns out that, in this situation, the approximation by the sparse grid is always equal or superior to the approximation by the singular value decomposition. The results in this article improve and generalize those from Griebel & Harbrecht (2014). Especially, we consider the approximation of functions from generalized isotropic <em>and</em> anisotropic Sobolev spaces.