421	RWTH Publication No: 465339        2013        IGPM421.pdf
TITLE	Approximation of High-Dimensional Rank One Tensors
AUTHORS	Markus Bachmayr, Wolfgang Dahmen, Ronald DeVore, Lars Grasedyck
ABSTRACT	Many real world problems are high-dimensional in that their solution is a func- tion which depends on many variables or parameters. This presents a computational challenge since traditional numerical techniques are built on model classes for func- tions based solely on smoothness. It is known that the approximation of smoothness classes of functions suffers from the so-called 'curse of dimensionality'. Avoiding this curse requires new model classes for real world functions that match applications. This has led to the introduction of notions such as sparsity, variable reduction, and reduced modeling. One theme that is particularly common is to assume a tensor struc- ture for the target function. This paper investigates how well a rank one function f (x 1,..., x d ) = f 1 (x 1 ) ··· f d (x d ), defined on Ω = [0, 1] d , can be captured through point queries. It is shown that such a rank one function with component functions f j in W∞r([0, 1]), can be captured (in L∞) to accuracy O(C (d, r)N -r ) from N well chosen point evaluations. The constant C (d, r) scales like d dr . The queries in our algorithms have two ingredients, a set of points built on the results from discrepancy theory and a second adaptive set of queries dependent on the information drawn from the first set. Under the assumption that a point z ∈ Ω with non-vanishing f(z) is known, the accuracy improves to O(dN-r).
KEYWORDS	query algorithms, high-dimensional approximation, separable functions, rate of approximation
DOI	10.1007/s00365-013-9219-x
PUBLICATION	Constructive Approximation April 2014, Volume 39, Issue 2, pp 385-395