Optimal algorithms for linear problems with Gaussian measures (Q1091082): Difference between revisions

Let H be a separable Hilbert space, S be a linear operator on H, \(\mu\) be a Gaussian measure on H with mean 0 and positive definite correlation operator. The following problem is considered: Given linear information Nf about Sf, one wants to construct ''optimal'' algorithms \(\phi\) such that the error E(\(\phi\) (Nf)-Sf) is minimal in the average sense (i.e., \(\int_{F_ 1}E(\phi (Nf)-Sf)\mu (df)\to \min)\) or in the probabilistic sense (i.e., \(\mu\) (\(\{\) f/E(\(\phi\) (Nf)-Sf)\(\leq \epsilon \})\to \sup\). for \(\epsilon >0)\), where E is a very general error functional. The ''uncertainty'' of a given information operator is defined as the error for optimal algorithms using this information operator. Both for the average and for the probabilistic case the following results are proven: For every adaptive information operator, there exists a non-adaptive information operator with at most the same uncertainty, i.e., adaptation does not help. Optimal algorithms can be constructed as (translated) spline algorithms, i.e., as special affine algorithms.