Approximation of two-variate functions: singular value decomposition versus sparse grids

Abstract

We compare the cost complexities of two approximation schemes for functions <em>f</em> ∈ <em>H^p</em>(<em>Ω</em>₁ × <em>Ω</em>₂) which live on the product domain <em>Ω</em>₁ × <em>Ω</em>₂ of sufficiently smooth domains <em>Ω</em>₁ ⊂ &#8477;^{<em>n</em>₁} and <em>Ω</em>₂ ⊂ &#8477;^{<em>n</em>₂} , namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. Here we assume that suitable finite element methods with associated <em>fixed</em> order <em>r</em> of accuracy are given on the domains <em>Ω</em>₁ and <em>Ω</em>₂. Then, the sparse grid approximation essentially needs only <em>O</em>(<em>ε</em>^{−<em>q</em>}) with <em>q</em> = ^{max{<em>n</em>₁,<em>n</em>₂}}/<em>_r</em> unknowns to reach a prescribed accuracy <em>ε</em> provided that the smoothness of <em>f</em> satisfies <em>p</em> ≥ <em>r</em>^{<em>n</em>₁+<em>n</em>₂}/_{max{<em>n</em>₁,<em>n</em>₂}</sup>} , which is an almost optimal rate. The singular value decomposition produces this rate only if <em>f</em> is analytical since otherwise the decay of the singular values is not fast enough. If p < <em>r</em>^{<em>n</em>₁+<em>n</em>₂}/_{max{<em>n</em>₁,<em>n</em>₂}</sup>} , then the sparse grid approach gives essentially the rate <em>O</em>(<em>ε</em>^{−<em>q</em>}) with <em>q</em> = ^{<em>n</em>₁,<em>n</em>₂}/_<em>p</em> while, for the singular value decomposition, we can only prove the rate <em>O</em>(<em>ε</em>^{−<em>q</em>}) with <em>q</em> = ^{2min{<em>r</em>,<em>p</em>}min{<em>n</em>₁,<em>n</em>₂}+2<em>p</em>max{<em>n</em>₁,<em>n</em>₂}}/ _{(2<em>p</em>−min{<em>n</em>₁,<em>n</em>₂})min{<em>r</em>,<em>p</em>}} . We derive the resulting complexities, compare the two approaches and present numerical results which demonstrate that these rates are also achieved in numerical practice.