Universität Jena, Mathematisches
Institut, Lehrstuhl Analysis
Dienstag, 24. Oktober 2000, 15.00 Uhr
Konferenzzimmer (R. 3319), Ernst-Abbe-Platz 1-4
(South Carolina, Columbia)
"Greedy Algorithms in Nonlinear
Our main interest in this talk is nonlinear approximation. The basic
idea behind nonlinear
approximation is that the elements used in the approximation do not come
from a fixed linear
space but are allowed to depend on the function being approximated. While
the scope of the talk
is mostly theoretical, we should note that this form of approximation
appears in many numerical
applications such as adaptive PDE solvers, compression of images and
classification, and so on.
The standard problem in this regard is the problem of $m$-term
approximation where one fixes a basis and looks to approximate a target
function by a linear
combination of $m$ terms of the basis. When the basis is a wavelet basis
or a basis of other
waveforms, then this type of approximation is the starting point for
compression algorithms. We
will discuss the quantitative aspects of this type of approximation. We
will also discuss
stable algorithms for finding good or near best approximations using $m$
These algorithms are representatives of a family of greedy algorithms.
More recently, there has emerged another more complicated form of
which we call highly nonlinear approximation. It takes many forms but
has the basic
ingredient that a basis is replaced by a larger system of functions that
is usually redundant.
Some types of approximation that fall into this general category are
adaptive pursuit (or greedy algorithms) and adaptive basis selection.
Redundancy on the one
hand offers much promise for greater efficiency in terms of approximation
rate, but on the
other hand gives rise to highly nontrivial theoretical and practical
We will discuss some of these theoretical problems in the talk.
Dr. D.D. Haroske; 2000-10-12