The Minimal Cost of Approximating Linear Operators Using Perturbed Information-The Asymptotic Setting

✍ Scribed by Bolesław Z. Kacewicz; Leszek Plaskota

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 675 KB
• Volume: 9
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.1993.1008

✦ Synopsis

We study the asymptotic behavior of the minimal cost of computing an (\varepsilon)-approximation to linear continuous operators, as (\varepsilon \rightarrow 0^{+}). An approximation is computed based on perturbed values of linear and continuous functionals which can be chosen adaptively. Obtaining a value of a functional with given precision is connected with some cost determined by the cost function. Under some assumptions, we show that the minimal (information) cost of computing an (\varepsilon)-approximation grows essentially as fast as the minimal information cost in the worst case setting. it can grow significantly slower only on a boundary set of problem elements. A nonadaptive method with the information cost proportional to the minimal worst case cost is constructed. & 1993 Academic Press, Inc.