Approximation of bi-variate functions: Singular value decomposition versus sparse grids

We compare the cost complexities of two approximation schemes for functions f∈Hp(O1×O2) which live on the product domain O1×O2 of sufficiently smooth domains O1⊂ℝn1 and O2⊂ℝn2, namely the singular value/Karhunen-Lòeve decomposition and the sparse grid representation. Here, we assume that suitable finite element methods with associated fixed order r of accuracy are given on the domains O1 and O2. Then, the sparse grid approximation essentially needs only 𝒪(e−q), with q=max{n1,n2}/r, unknowns to reach a prescribed accuracy e, provided that the smoothness of f satisfies p>r((n1+n2)/max{n1,n2}), 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 ((n1+n2)/max{n1,n2}), then the sparse grid approach gives essentially the rate 𝒪 (e−q) with q=(n1+n2)/p, while, for the singular value decomposition, we can only prove the rate 𝒪(e−q) with q=(2 min{r,p}min{n1,n2} +2p max{n1,n2}){(2p−min{n1,n2}) 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.