MC 5501
Speaker
Edward Vrscay | Applied Mathematics, University of Waterloo
Title
The "Waterloo Fractal Analysis and Coding Project”: Generalized fractal transforms, contraction maps and associated inverse problems, and like, some other stuff
Abstract
Originally inspired by the work of B. Mandelbrot, who showed that classic “fractal" sets could be viewed as unions of contracted copies of themselves, as well as the later idea that fractal sets can be generated by systems of contraction mappings, our “Waterloo Fractal Coding and Analysis Project" has, over the past (over) 30 years, been interested in “generalized fractal transforms" (GFTs) over various spaces and their applications (e.g., imaging) and associated inverse problems. In the spirit of a colloquium talk aimed at a general audience of faculty and students, I shall provide an overall summary of some of our work outlining its history and results as well as the people and the collaborations: who, where, when and how.
A GFT, T, defined on a complete metric space (X,d), acts on an element x in (X,d) in the following way: It first makes N modified copies of x (e.g., spatially-contracted, range-transformed and translated), and then combines these "fractal components” in a manner appropriate to the space X, to produce a new element y = Tx. Under certain conditions, the operator T is contractive on X which, from Banach's Fixed Point Theorem, implies the existence of a unique fixed point p = Tp. From the action of T, p is "self-similar" in the sense that it is an appropriate combination of modified copies of itself.
This naturally leads to the following inverse problem associated with contraction mappings: Let Con(X) be a class of contraction maps on a complete metric space (X,d) (e.g. GFT's). Then given an x in X, can one find a map T in Con(X) with fixed point p sufficiently close to x? This is the essence of fractal image coding and compression: We approximate an image x with p but we don't store p -- we store the parameters that define T, the so-called “fractal code" of x. The approximation p can then be generated by iteration of T.
The so-called "collage coding" method that we employ to determine such optimal contraction maps -- which is based on a trivial consequence of Banach's Theorem — may also be employed very effectively in “nonfractal" situations, for example, inverse problems (parameter estimation) in ODEs, PDEs, SDEs and inclusions. In fact, it didn't take long for the nonfractal applications to outnumber the fractal ones!
Finally, I shall report briefly on a couple of quite recent developments: (i) range-based function approximation and (ii) differential equations over fractal sets and measures.