Part of the Long Program Multiscale Geometry and Analysis in High Dimensions

October 19 - 23, 2004

The workshop on Multiscale Geometry in Scientific Computing is centered around two main themes: (1) the design of multiscale representations of operators allowing the speed up of fundamental computations and (2) the development of probabilistic and geometric tools allowing efficient matching and searching in high-dimensions.

Clever representation of scientific and engineering computations can make previously intractable computations tractable. In any problem with many variables, one attempts to find a description at any given length scale and to recursively construct a sequence of such descriptions at increasingly coarser scales. A typical multiscale approach would then combine local processing at each scale with inter-scale interactions. The advantages of such strategies include: (1) the possibility of calculating the coarse-scale behavior on coarse grids effectively, by using information previously gathered from finer grids; and (2) the possibility of employing the fine scales very sparingly, by adaptively refining selected regions where the solution of interest exhibits an interesting behavior. In fact, a whole host of new multiscale representations (“multiresolution,” “multilevel,” “multigrid”) has been proposed in recent years, each adapted to a special setting, ranging from n-body simulations, to electromagnetics and potential calculations to wave equations and thin-shell simulations.

In this workshop, we will gather together experts in important scientific and engineering computations and also in their multiscale representation. Although spatial multiscaling is still a very active area of research, its advantages are by now fairly well-understood and one would like to discuss ideas beyond the traditional scale-space viewpoint; examples might include promising new multiscale geometric representations of phase-space. Clearly, the opportunities that might be offered by comparable multiscale methods adapted to the geometry of the underlying solution space or of the operator one wish to represent could be very large.

A very active area of research in computer science nowadays is concerned with the design and analysis of approximation algorithms for computationally hard problems in combinatorial optimization. As an example of such problems, one can consider clustering algorithms or the nearest neighbor search; the latter, for example, consists in the design of a data structure which would find the closest point—taken from a large collection of possibly very high-dimensional datapoints—to an arbitrary input. Such problems have many applications in fields as diverse as (computational) statistics, pattern recognition, vector compression, routing and flow control in communication networks, multimedia information retrieval, and so on. Building upon the celebrated result of Johnson-Lindenstrauss (which says that n points in an n-dimensional space can be embedded into a space of approximate dimension log(n) proviso a negligible distortion of the paired distances), a community of researchers has developed a remarkable understanding of such problems, showing that often times, it is possible to design low complexity algorithms which return good approximate answers. This workshop will gather experts in this exploding area of high-dimensional geometric computations.

A higher goal of this workshop is to show how each area can be influenced by accomplishments in the other, and influence in turn, progress in multiscale computations, and scientific and engineering computations in general.

Gregory Beylkin, Chair
(University of Colorado, Dept. of Applied Math)

Emmanuel Candes, Chair
(California Institute of Technology, Applied and Computational Mathematics)

Rafail Ostrovsky
(UCLA, Computer Science)

Guillermo Sapiro
(University of Minnesota, Mathematics)