O przekleństwie wymiaru dla wielowymiarowych zadań ciągłych

Wiele zadań d-wymiarowych cierpi na przekleństwo wymiaru co znaczy, że minimalna liczba obliczeń potrzebna dla znalezienia przybliżenia jest wykładnicza w d. To może się zdarzyć nawet dla zadań bardzo gładkich jak będzie zilustrowane zadaniem aproksymacji wielowymiarowej dla funkcji C_∞. Naturalnym pytaniem jest co robić w tej sytuacji? Ponieważ przekleństwo wymiaru jest wynikiem złożonowościowym, jedynym sposobem pozbycia się przekleństwa jest ograniczenie zadania do mniejszej klasy lub zrelaksowanie pojęcia błędu czy też wprowadzenie podwyższonej gładkości ze względu na kolejne zmienne. To będzie także zilustrowane w czasie wykładu.

Many d-variate problems suffer the curse of dimensionality which means that the minimal number of evaluations nedeed to find an approximation is exponential in d. This can happen even for very regular problems as will be illustrated for multivariate approximation of C_∞ functions. The natural question is what to do? Since the curse of dimensionality is a complexity result the only way to vanguish the curse is to shrink the problem or to relax the notion of error or to increase smoothness with respect to successive variables. This also will be illustrated in the talk.