Browse Prior Art Database

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

IP.com Disclosure Number: IPCOM000148194D
Original Publication Date: 1982-May-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Wasilkowski, G.W.: AUTHOR [+2]

Abstract

G. W. Wasilkowski

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 16% of the total text.

Page 1 of 32

 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 1982
Revised May 1-983

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

[This page contains 1 picture or other non-text object]

Page 2 of 32

Abstract

    In this paper we study the following problem. Given an operator s and a subset F of some linear space, approximate

0

~ ( f )

    for any f E Fo possessing only partial information on f. Although all operators S considered here are

that these problems are "equivalent" to the problem of approximating S ( f ) = f , i. e. , S = I. This equivalence pro- vides optimal (or nearly optimal) information and algorithms.

[This page contains 1 picture or other non-text object]

Page 3 of 32

1. Introduction
There are many Fapers dealing with the following

problem: approximate an elenent f which belongs to a
subclass FO of a linear normed space possessing only partial
information on f. For many subclasses Fo we know optimal
information, optimal algorithals and we krow that adaptive
information is not more ?owerful than nonadantive infomation.
(see e.g. Cl', [ 4 ! ) . 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 nroblern of
finding optimal information and optimal algorithms more dif-
ficult.

    In this pa?er we give sufficient conditions for a non-
linear problem to be equivalent to the problem of approximating
S(f) = f. This equivalence leads to optimal (or nearly optimal)
information and algoritk~s
for this nonlinear ?roblent. We will
present some nonlinear problems for which these sufficient
conditions hold.

    We summarize the contents of this Taper. 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,

[This page contains 1 picture or other non-text object]

Page 4 of 32

information and an algorithm. W e recall the concept of the error of an algorithm and of the radius of information. W e

show how these concepts become simpler for the problem with
s = I i. e., S (f) = f. In Section 3 we prove two simple
lemmas which give sufficient conditions for a nonlinear pro- blem to be equivalent to the prcblem with S = I. W e illustrate

1

these lemmas by such problems as approximation of S ( f ) - - - f

or S (f) = J f where f is a function. In Section 4 we consider the problem of estimating S(f) = jlfjl. In the last section w e 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 alg...