Singular value decomposition versus sparse grids: Refined complexity estimates

Griebel, Michael and Harbrecht, Helmut. (2019) Singular value decomposition versus sparse grids: Refined complexity estimates. IMA journal of numerical analysis, 39 (4). pp. 1652-1671.

[img] PDF - Published Version
Restricted to Repository staff only until 12 July 2021.


Official URL: https://edoc.unibas.ch/72270/

Downloads: Statistics Overview


We compare the cost complexities of two approximation schemes for functions that live on the product domain Ω1×Ω2"> Ω_ 1 × Ω _ 2 of sufficiently smooth domains Ω1⊂Rn1"> Ω Ω1×Ω2"> _ 1 ⊂ ℝ^{ n_ 1} and Ω2⊂Rn2"> Ω Ω1×Ω2"> _ 2 ⊂ ℝ^{ n_ 2} ⁠, namely the singular value / Karhunen-Lòeve decomposition and the sparse grid representation. We assume that appropriate finite element methods with associated orders r1"> r Ω1×Ω2"> _ 1 and r2"> r Ω1×Ω2"> _ 2 of accuracy are given on the domains Ω1"> Ω Ω1×Ω2"> _ 1 and Ω2"> Ω Ω1×Ω2"> _ 2 ⁠, 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 the study by Griebel & Harbrecht (2014, Approximation of bi-variate functions. Singular value decomposition versus sparse grids. IMA J. Numer. Anal. , 34 , 28-54). Especially, we consider the approximation of functions from generalized isotropic and anisotropic Sobolev spaces.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Mathematik > Computational Mathematics (Harbrecht)
UniBasel Contributors:Harbrecht, Helmut
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:Oxford University Press
Note:Publication type according to Uni Basel Research Database: Journal article
Identification Number:
edoc DOI:
Last Modified:20 Nov 2019 16:04
Deposited On:11 Nov 2019 08:32

Repository Staff Only: item control page