Browse Prior Art Database

Some Nonlinear Operators Are As Easy To Approximate As The Identity Operator

IP.com Disclosure Number: IPCOM000127973D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 25 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

G.W. Wasilkowski: AUTHOR [+3]

Abstract

In this paper we study the following problem. Given an operator S and a subset F0 of some linear space. approximate S(f) for any f e F0 possessing only partial information on f. Although all operators S considered here are nonlinear (e. g. [Equation ommitted] we prove that these problems are "equivalent" to the problem of approximating [Equation ommitted] This equivalence pro-vides optimal (or nearly optimal) information and algorithms. e

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 17% of the total text.

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Some Nonlinear Operators Are As Easy To Approximate As The Identity Operator

G.W. Wasilkowski

Department of Computer Science Columbia University New York, New York

May 1981

Revised May 1.983

This research was supported in part by the National Science Foundation under Grant MCS 82- 14322.

Abstract

In this paper we study the following problem. Given an operator S and a subset F0 of some linear space. approximate S(f) for any f e F0 possessing only partial information on f. Although all operators S considered here are nonlinear (e. g.

(Equation Omitted)

we prove that these problems are "equivalent" to the problem of approximating

(Equation Omitted)

This equivalence pro-vides optimal (or nearly optimal) information and algorithms. e

1. Introduction

There are many papers dealing with the following problem: approximate an element f which belongs to a subclass F0 of a linear normed space possessing only partial information on f. For many subclasses F0 we know optimal information, optimal algorithms and we know that adaptive information is not more powerful than nonadantive information. (see e.g.

(Equation Omitted)

) . This is an example of a linear problem; that is one wants to approximate S(f) for a linear operator S.

The situation is quite different for nonlinear problems that is one wants to approximate S(f) where S is a nonlinear operator. Nonlinearity of S usually makes the Problem of finding optimal information and optimal algorithms more difficult. In this paper we give sufficient conditions for a non-linear Problem to be equivalent to the problem of approximating

(Equation Omitted)

Columbia University Page 1 Dec 31, 1983

Page 2 of 25

Some Nonlinear Operators Are As Easy To Approximate As The Identity Operator

. This equivalence leads to optimal (or nearly optimal)

information and algorithms for this nonlinear problem. We will

present some nonlinear problems; for which these sufficient conditions hold. We summarize the contents of this paper. In Section 2 we present the basic definitions and results which will be needed in this paper. We define what we mean by a problem, information and an algorithm. We recall the concept of the error of an algorithm and of the radius of information. We show how these concepts become simpler for the problem with

(Equation Omitted)

. in Section 3 we prove two simple lemmas which give sufficient conditionsfor a nonlinear pro- blem to be equivalent to the problem with S = I. we illustrate

these lemmas by such problems as approximation of

(Equation Omitted)

where f is a function. In Section 4 we consider the problem o f estimating

(Equation Omitted)

in the last section we study three problems which are related to the problem of finding the minimum of a given function f. For all these problems we exhibit nearly optimal infor-mation and nearly optimal algorithms. We also prove that adoption does not help. r

2. Basic concepts.

In this secti...