November 30 – December 5 , 2008, Dagstuhl Seminar 08492

Structured Decompositions and Efficient Algorithms


Stephan Dahlke (Universität Marburg, DE)
Ingrid Daubechies (Princeton University, US)
Michael Elad (Technion – Haifa, IL)
Gitta Kutyniok (Universität Osnabrück, DE)
Gerd Teschke (Hochschule Neubrandenburg, DE)

For support, please contact

Dagstuhl Service Team


List of Participants


New emerging technologies such as high-precision sensors or new MRI machines drive us towards a challenging quest for new, more effective, and more daring mathematical models and algorithms. Therefore, in the last few years researchers have started to investigate different methods to efficiently represent or extract relevant information from complex, high dimensional and/or multimodal data. Efficiently in this context means a representation that is linked to the features or characteristics of interest, thereby typically providing a sparse expansion of such. Besides the construction of new and advanced ansatz systems the central question is how to design algorithms that are able to treat complex and high dimensional data and that efficiently perform a suitable approximation of the signal. One of the main challenges is to design new sparse approximation algorithms that would ideally combine, with an adjustable tradeoff, two properties: a provably good `quality' of the resulting decomposition under mild assumptions on the analyzed sparse signal, and numerically efficient design.

The topic is driven by applications as well as by theoretical questions. Therefore, the aim of this seminar was to bring together a good mixture of scientists with different backgrounds in order to discuss recent progress as well as new challenging perspectives. In particular, it was intended to strengthen the interaction of mathematicians and computer scientists.

The goals of the seminar can be summarized as follows::

  • Initiate communications between different focuses of research.
  • Comparison of methods.
  • Open new areas of applications.
  • Manifest the future direction of the field.

This seminar was regarded by the participants as a very productive and inspiring meeting. Many intense discussions took place throughout the week, and several new cooperations were initiated. Especially, the interactions between computer scientists and applied mathematicians has been extremely fruitful and will certainly be continued in the future. Also, the major future directions of this research area were manifested and initial steps towards solutions undertaken. Concluding, this seminar can be regarded as a milestone in the development of the new, rapidly evolving research area of Structured Decompositions and Efficient Algorithms.

Last, but not least, the success of this seminar is in main parts due to the great scientific atmosphere offered by Schloss Dagstuhl, for which we would like to thank the scientific as well as administrative staff at Schloss Dagstuhl.

Related Dagstuhl Seminar


  • Data Bases
  • Information Retrieval
  • Data Structures
  • Algorithms
  • Complexity
  • Sparse Signal Representation
  • Signal Reconstruction
  • Signal Compression


  • Sparse signal representation
  • Optimal signal reconstruction
  • Approximation
  • Compression


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.