FoCM 2014 conference

Session B5 - Information Based Complexity

Organizers: Stefan Heinrich (University of Kaiserslautern, Germany) - Aicke Hinrichs (Friedrich Schiller University Jena, Germany)

Workshop website

View session abstracts PDF



December 15, 14:30 ~ 15:00 - Room B23

The ANOVA decomposition of a non-smooth function of an infinite number of variables

Ian Sloan

University of New South Wales, Australia   -

In this work we extend our earlier work motivated by path-dependent option pricing problems, in which we tried to understand how it is that sparse grid and QMC methods can be applied successfully to option pricing problems, even though the integrands do not live in any mixed derivative smoothness class. That difficulty derives from the ``max function'' in the integrand, describing the fact that options are considered worthless if the payoff falls below the strike price.

In a previous paper (Math. Comp. 82, 383-400, 2013) we showed that if the expected value is expressed as an integral over $\mathbb{R}^d$ then the classical ANOVA decomposition of the integrand for an arithmetic Asian option can have every term smooth except for the very highest term. That highest ANOVA term has many discontinuities in first partial derivatives, but in most cases is expected to be pointwise very small.

In the present work we consider the ANOVA decomposition of the corresponding continuous problem in the Brownian bridge (or Levy-Ciesielski) formulation, and show that in this case \textbf{every term in the (infinite) ANOVA decomposition is smooth.} With this result we are preparing for an error analysis of the cubature problem for option pricing problem, in which the discrete-time problem is approximated by the continuous problem, and the error analysis then applied to the truncated infinite ANOVA expansion, in which every term is smooth.

Joint work with Frances Kuo (UNSW), Michael Griebel (Bonn).

View abstract PDF

December 15, 15:00 ~ 15:30 - Room B23

On equivalence of anchored and ANOVA spaces of multivariate functions

Mario Hefter

University of Kaiserslautern, USA   -

We consider anchored and ANOVA spaces of functions with mixed first order partial derivatives bounded in $L_1$ and $L_\infty$ norms. The spaces are weighted and we provide necessary and sufficient conditions so that the corresponding spaces have equivalent norms with constants independent of the number of variables. This includes the case of countably many variables.

Joint work with Grzegorz Wasilkowski.

View abstract PDF

December 15, 15:30 ~ 16:00 - Room B23

$L_p$-spaces in the anchored and ANOVA setting

Aicke Hinrichs

Johannes Kepler University Linz, Austria   -

We extend the recent investigation of G. Wasilkowski on the equivalence of weighted anchored and ANOVA $L_1$ and $L_\infty$ norms of function spaces with mixed partial derivatives of order one. Among other norms, we consider $L_p$ norms for $1\le p\le \infty$ and confirm the conjecture that for product weights, summability of the weight sequence is necessary and sufficient.

Joint work with Jan Schneider (University of Rostock, Germany).

View abstract PDF

December 15, 16:00 ~ 16:30 - Room B23

Integration w.r.t. the Standard Gaussian Measure on the Sequence Space

Mario Hefter

TU Kaiserslautern, Germany   -

We consider a quadrature problem on the sequence space $\mathbb R^{\mathbb N}$, where the underlying measure $\mu=N(0,1)^{\mathbb N}$ is given by the countable product of standard normal distributions and the integrands $f:\mathbb R^{\mathbb N}\to\mathbb R$ belong to a unit ball of a reproducing kernel Hilbert space. This space has tensor product form, and the building blocks are weighted Sobolev spaces of once differentiable functions where the function itself and the derivative have bounded $L^2$-norm with respect to the centered normal distribution $N(0,\sigma^2)$ with variance $\sigma^2$.

We consider deterministic algorithms in the worst-case-setting, where the cost of evaluating a function at a point is the index of the highest nonzero component. Upper and lower bounds for the complexity are derived.

View abstract PDF

December 15, 17:00 ~ 17:30 - Room B23

Tractability of the Approximation of High-Dimensional Rank One Tensors

Erich Novak

Jena University , Germany   -

We study the approximation of high-dimensional rank one tensors using point evaluations. We prove that for certain parameters (smoothness and norm of the $r$th derivative) this problem is intractable while for other parameters the problem is tractable and the complexity is only polynomial in the dimension. We completely characterize the set of parameters that lead to easy or difficult problems, respectively. In the ``difficult'' case we modify the class to obtain a tractable problem: The problem gets tractable with a polynomial (in the dimension) complexity if the support of the function is not too small.

Joint work with Daniel Rudolf (Jena University, Germany).

View abstract PDF

December 15, 17:30 ~ 18:00 - Room B23

On the complexity of scalar first order PDEs

Stefan Heinrich

University of Kaiserslautern, Germany   -

Within the framework of information-based complexity theory, we study the approximate solution of certain classes of scalar first order partial differential equations, both in the deterministic and the randomized setting. We consider standard information. The analysis is based on the classical method of characteristics and on recent results by Th. Daun and the author on the complexity of parametric ordinary differential equations. We also discuss the case of first order PDEs depending on parameters.

View abstract PDF

December 15, 18:00 ~ 18:30 - Room B23

Tractability of approximation of ridge functions

Jan Vybiral

Department of Mathematical Analysis, Charles University, Prague, Czech R