Several approaches to break the curse of dimensionality

Weimar, Markus

In modern science the 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 can not 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 arbitrary 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 thesis is to present several approaches of this type. Moreover, a detailed introduction to the field of IBC is given.

In den modernen Wissenschaften gewinnt die effiziente numerische Behandlung hochdimensionaler Aufgabenstellungen zunehmend an Bedeutung. Eine fundamentale Erkenntnis der informationsbasierten Komplexitätstheorie ist es, dass die Kompliziertheit eines Problems durch die Konvergenzrate allein nicht hinreichend beschrieben werden kann. Beispielsweise existieren Probleme, deren algorithmische Lösung trotz beliebig guter Konvergenzrate exponentiell viele Informationsoperationen benötigt. In so einem Fall spricht man vom Fluch der Dimension bzw. dem Curse of Dimensionality. Bei der analytischen Untersuchung numerischer Probleme stellt sich heraus, dass dieser Fluch oftmals durch die Ausnutzung zusätzlicher Struktureigenschaften überwunden werden kann. Neben einer detailierten Einführung in die Theorie strebt die vorliegende Arbeit an, verschiedene solche Ansätze vorzustellen.

Zitieren

Zitierform:

Weimar, Markus: Several approaches to break the curse of dimensionality. 2013.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Export