Browse Prior Art Database

MEASURING UNCERTAINTY WITHOUT A NORM

IP.com Disclosure Number: IPCOM000127967D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 9 page(s) / 23K

Publishing Venue

Software Patent Institute

Related People

Arthur G. Werschulz: AUTHOR [+3]

Abstract

Traub, Wasilkowski, and Wozniakowski have shown how un-certainty can be defined and analyzed withQut a norm or metric. Thier theory is based on two natural and non-restrictive axioms. We show that these axioms induce a family of pseudometrics, and that balls of radius e are (roughly) the e-approximations to the solution. In addition, we show that a family of pseudometrics is necessary, even for the problem of computing x such that [Equation ommitted] where f is a real function.

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

Page 1 of 9

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

MEASURING UNCERTAINTY WITHOUT A NORM

by

Arthur G. Werschulz

Division of Science and Mathematics Fordham University/College at Lincoln Center New York, N.Y. 10023 and

Department of Computer Science Columbia University New York, N.Y. November, 1982

CIO

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

Abstract

Traub, Wasilkowski, and Wozniakowski have shown how un-certainty can be defined and analyzed withQut a norm or metric. Thier theory is based on two natural and non-restrictive axioms. We show that these axioms induce a family of pseudometrics, and that balls of radius e are (roughly) the e-approximations to the solution. In addition, we show that a family of pseudometrics is necessary, even for the problem of computing x such that

(Equation Omitted)

where f is a real function.

1. Introductiain

in two recent monographs ([3],[4]), Traub and his c I olleagues have studied the optimal solution of problems which are solved approximately, that is, where there is uncertainty in the answer. in [41, uncertainty was measured by a norm. For some problems, this is not an appropriate or natural assumption. Therefore, in (31 it is shown how uncertainty can be introduced via two natural and non-restrictive axioms.

In a private communication, Traub asked about the strength of these axioms. That is, do the axioms generate any interesting structures? In Section 2 of this paper, we show that these axioms induce a family of pseudometrics. Moreover, we show that the balls of radius e generated by this family of pseudometrics are (roughly speaking) the e-approximations to the solution.

is a family of pseudometrics necessary? We give an affirmative answer in Section 3, using the problem of computing x such that If

(Equation Omitted)

Columbia University Page 1 Dec 31, 1982

Page 2 of 9

MEASURING UNCERTAINTY WITHOUT A NORM

: , where f is a real f unction.

2. solution 2"erators Are G&nerated Y Families of Pseudometrics

We first recall the definition of a solution operator from [3]. Let F and G be sets, and let 2G denote the power set of G, i.e., the class of all subsets of G. Let IR + denote the non- negative real numbers. if S : F x1R + 2G is an operator such that

(2.1)

(Equation Omitted)

and

(2.2)

(Equation Omitted)

then S is said to be a solution operator, and S(f,E:) is said to be the set of e-approximations to the (exact) solution S(f,O).

Note that S(f,e) is a set. This formulation allows the exact solution S(f,O) to be a set, i.e., a problem may have multiple solutions. in addition, S(f,e) a set means that we are willing to accept any element of S(f,e) a s an :-approximation. These axioms are very natural: the first says that every problem has a solution, while the second says that increasing the uncertainty cannot decrease the family of z-approximations.

In order to clarify these notions we give three examples.

Exam2le 2.1- Let F be a se...