1983 Reports

# Some Nonlinear Operators Are as Easy to Approximate as the Identity Operator

In this paper we study the following problem. Given an operator S and a subset FO of some linear space, approximate S(f) for any f E FO possessing only partial information on f. Although all operators S considered here are nonlinear (e.g. minf(x), minlf(x), 1/f or lI f lI), we prove that these problems are "equivalent" to the problem of approximating S(f) = f, i.e., S = I. This equivalence provides optimal (or nearly optimal) information and algorithms.

## Subjects

## Files

- cucs-058-83.pdf application/pdf 588 KB Download File

## More About This Work

- Academic Units
- Computer Science
- Publisher
- Department of Computer Science, Columbia University
- Series
- Columbia University Computer Science Technical Reports, CUCS-058-83
- Published Here
- October 25, 2011