Breaking the curse of dimensionality

Markus Weimar. Breaking the curse of dimensionality. 2015. <http://eudml.org/doc/286045>.

@book{MarkusWeimar2015,
abstract = {In modern science, efficient numerical treatment of high-dimensional problems becomes more and more important. A fundamental insight of the theory of information-based complexity (IBC for short) is that the computational hardness of a problem cannot be described properly only by the rate of convergence. There exist problems for which an exponential number of information operations is needed in order to reduce the initial error, although there are algorithms which provide an arbitrarily large rate of convergence. Problems that yield this exponential dependence are said to suffer from the curse of dimensionality. While analyzing numerical problems it turns out that we can often vanquish this curse by exploiting additional structural properties. The aim of this paper is to present several approaches of this type. Moreover, a detailed introduction to the field of IBC is given.},
author = {Markus Weimar},
keywords = {curse of dimensionality; tractability; information-based complexity; tensor products; high-dimensional approximation; product weights; worst case error},
language = {eng},
title = {Breaking the curse of dimensionality},
url = {http://eudml.org/doc/286045},
year = {2015},
}

TY - BOOK
AU - Markus Weimar
TI - Breaking the curse of dimensionality
PY - 2015
AB - In modern science, efficient numerical treatment of high-dimensional problems becomes more and more important. A fundamental insight of the theory of information-based complexity (IBC for short) is that the computational hardness of a problem cannot be described properly only by the rate of convergence. There exist problems for which an exponential number of information operations is needed in order to reduce the initial error, although there are algorithms which provide an arbitrarily large rate of convergence. Problems that yield this exponential dependence are said to suffer from the curse of dimensionality. While analyzing numerical problems it turns out that we can often vanquish this curse by exploiting additional structural properties. The aim of this paper is to present several approaches of this type. Moreover, a detailed introduction to the field of IBC is given.
LA - eng
KW - curse of dimensionality; tractability; information-based complexity; tensor products; high-dimensional approximation; product weights; worst case error
UR - http://eudml.org/doc/286045
ER -