Proceedings of the International Congress of Mathematicians
Madrid, August 22–30, 2006
Full-Text PDF (188 KB) |
Book articles | Book details
pp: 187–215
DOI: 10.4171/022-1/9
A large portion of computation is concerned with approximating a function u. Typically, there are many ways to proceed with such an approximation leading to a variety of algorithms. We address the question of how we should evaluate such algorithms and compare them. In particular, when can we say that a particular algorithm is optimal or near optimal? We shall base our analysis on the approximation error that is achieved with a given (computational or information) budget n. We shall see that the formulation of optimal algorithms depends to a large extent on the context of the problem. For example, numerically approximating the solution to a PDE is different from approximating a signal or image (for the purposes of compression).
Keywords: Optimal computation, encoding and compression, learning theory, entropy and widths