The Complexity of Fredholm Equations of the Second Kind: Noisy Information About Everything

Werschulz, Arthur G.

We study the complexity of Fredholm problems of the second kind u − Ω k(·, y)u(y) dy = f . Previous work on the complexity of this problem has assumed that Ω was the unit cube Id. In this paper, we allow Ω to be part of the data specifying an instance of the problem, along with k and f. More precisely, we assume that Ω is the diffeomorphic image of the unit d-cube under a Cr1 mapping ρ Id → Il. In addition, we assume that k ∈ Cr2 (I2l) and f ∈ Wr3,p(Il) with r3 > l/p. Our information about the problem data is contaminated by δ-bounded noise. Error is measured in the Lp-sense. We find that the nth minimal error is bounded from below by Θ(n−μ1 + δ) and from above by Θ(n−μ2 + δ), where
μ1 = min r1 , r2 , r3 − (d − l)/p and μ2 = min r1 − ν , r2 , r3 − (l − d)/p , d2d d d2d d
with d
ν=p ifr1 ≥2,r2 ≥2, and d≤p,
1 otherwise.
In particular, the nth minimal error is proportional to Θ(n−μ1 +δ) when p = ∞. The upper bound is attained by a noisy modified Galerkin method, which can be efficiently implemented using multigrain techniques. We thus find bounds on the ε-complexity of the problem, these bounds depending on the cost c(δ) of calculating a δ-noisy function value. As an example, if c(δ) = δ−b, we find that the ε-complexity is between (1/ε)b+1/μ1 and (1/ε)b+1/μ2 .



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-003-04
Published Here
April 26, 2011