Approximation of two-variate functions: singular value decomposition versus sparse grids
Approximation of two-variate functions: singular value decomposition versus sparse grids
View/Date of Publication
2011Publisher
Institut für Numerische Simulation (INS)Publisher Location
BonnMetadata
Show full item record
Citable Link (Handle URI) 
https://hdl.handle.net/20.500.11811/11958
Abstract
We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝ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 Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{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.
Subjects
singular value decomposition, sparse grids, complexity
Classification (DDC)
510 Mathematik 518 Numerische AnalysisFirst Publication
https://ins.uni-bonn.de/publication/preprintsRelated Publications
https://doi.org/10.1093/imanum/drs047Part of Series
INS Preprints ; 1109Griebel, Michael; Harbrecht, Helmut: Approximation of two-variate functions: singular value decomposition versus sparse grids. In: INS Preprints, 1109.
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11958
Online-Ausgabe in bonndoc: https://hdl.handle.net/20.500.11811/11958
@unpublished{handle:20.500.11811/11958,
author = {{Michael Griebel} and {Helmut Harbrecht}},
title = {Approximation of two-variate functions: singular value decomposition versus sparse grids},
publisher = {Institut für Numerische Simulation (INS)},
year = 2011,
INS Preprints},
volume = 1109,
note = {We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝ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 Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{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.},
url = {https://hdl.handle.net/20.500.11811/11958}
}
author = {{Michael Griebel} and {Helmut Harbrecht}},
title = {Approximation of two-variate functions: singular value decomposition versus sparse grids},
publisher = {Institut für Numerische Simulation (INS)},
year = 2011,
INS Preprints},
volume = 1109,
note = {We compare the cost complexities of two approximation schemes for functions f ∈ Hp(Ω1 × Ω2) which live on the product domain Ω1 × Ω2 of sufficiently smooth domains Ω1 ⊂ ℝn1 and Ω2 ⊂ ℝ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 Ω1 and Ω2. Then, the sparse grid approximation essentially needs only O(ε−q) with q = max{n1,n2}/r unknowns to reach a prescribed accuracy ε provided that the smoothness of f satisfies p ≥ rn1+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 < rn1+n2/max{n1,n2} , then the sparse grid approach gives essentially the rate O(ε−q) with q = n1,n2/p while, for the singular value decomposition, we can only prove the rate O(ε−q) with q = 2min{r,p}min{n1,n2}+2pmax{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.},
url = {https://hdl.handle.net/20.500.11811/11958}
}
The following license files are associated with this item:
