Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

LOCAL AVERAGZ ERROR

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

Publishing Venue

Software Patent Institute

Related People

G.W. Wasilkowski: AUTHOR [+3]

Abstract

An average case setting for linear problems has been studied in a series of recent papers. optimal algorithms and optimal information were obtained for certain probability measures. in this paper the local average error of algorithms and local average radius of information are defined. Using these concepts, optimal Lnformation and optimal algorithms can be found for nonlinear problems and arbitrary Borel measures.

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

Page 1 of 34

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

LOCAL AVERAGZ ERROR

G.W. Wasilkowski

0epartmont of Computer Science Columbia University Now York, New York

August 1983

This research was supported in part by the National Science Foundation under Grant mcs- 7823676.

r,t) 8

AbstraCt

An average case setting for linear problems has been studied in a series of recent papers. optimal algorithms and optimal information were obtained for certain probability measures. in this paper the local average error of algorithms and local average radius of information are defined. Using these concepts, optimal Lnformation and optimal algorithms can be found for nonlinear problems and arbitrary Borel measures.

1. introduction

The average case setting for linear problems is studied in [4,7,81. more precisely, the (global) average error of an algorithm and the (global) average radius of information are defined and optimal algorithms and information are found for certain probability measures. Zn this paper we define the local average error and the local average radius. Analogous concepts occur, for example, in statistics, where they are used primarily for discrete and finite dimensional problems. Since we are primarily interested in infinite dimensional problems, we study the local average error and radius in an abstract setting. it is often assumed that the local average radius is a measurable function. We want to establish rather than assume the measurability of the local average radius since this is crutial to our study. We motivate our interest in the local average error and the local average radius. These concepts (i) lead to formulas which, in principle, give an optimal algorithm and optimal information for nonlinear problems and arbitrary Borel measure. whether this leads to "practical,, formulas depends on the problem. (ii) enable us to study any algorithm, in general nonmeasurable. The measurability of optimal algorithms is proven, not assumed.

The results reported in this paper are primarily of theoretical interest. They will be applied to a variety of problems in future papers, the flavor of which is discussed in Section 6.

we summarize the contents of the paper. In Sections 2,3,4 we deal with problems defined on separable Banach spaces. This is only for simplicity; a generalization is discussed in Section S. in Section 2 we recall properties of conditional measure which are crutial for our study. In Section 3 we define our basic concepts and prove that the local average radius and the local average error of any optimal algorithm are measurable. in Section 4 we illustrate these concepts

Columbia University Page 1 Dec 31, 1983

Page 2 of 34

LOCAL AVERAGZ ERROR

for an orthogonally invariant measure, We exhibit optimal algorithms and optimal information and we establish some important properties of orthogonally invariant measures. In Section 5 we generalize all results to the case where the error is not necessarily measured by a no...