Sparsity and Computation

Organizers: Ron DeVore (Texas A&M University), Massimo Fornasier (RICAM Linz), Holger Rauhut (Hausdorff Center for Mathematics, University of Bonn)

Venue: Mathematik-Zentrum, Lipschitz Lecture Hall, Endenicher Allee 60, Bonn

Dates: June 7 - 11, 2010


Sparsity has become a very important concept in recent years in applied mathematics, especially in mathematical signal and image processing, in the numerical treatment of PDEs as well as in inverse problems. The key idea is that many types of functions and signals arising naturally in these contexts can be described by only a small number of significant degrees of freedom. The workshop will focus in particular on compressive sensing, low rank approximation and matrix completion, adaptive numerical solution of operator equations exploiting sparsity as well as on high-dimensional data analysis.

Compressive sensing is a new field which has seen enormous interest and growth. Quite surprisingly, it predicts that sparse high-dimensional signals can be recovered efficiently from what was previously considered highly incomplete measurements. This discovery has led to a fundamentally new approach to certain signal and image recovery problems. Remarkably, mainly random constructions for good measurement matrices are known so far, and the mathematical research in compressive sensing uses tools from probability theory and geometry of Banach spaces.

Rank minimization has its roots in image compression algorithms, learning theory, and collaborative filtering. An important special case is described by the matrix completion problem, where one has only a few observations of the entries of a low-rank matrix and tries to complete the missing entries. Quite surprising recent results in this direction prove that this is indeed possible by using efficient algorithms, such as convex relaxation.

In many cases a function or signal is only given implicitly in terms of an operator equation. Optimal adaptive methods for computing the nearly best sparse approximation with respect to a given multiscale basis, e.g., wavelets, have been investigated in the last decade. It is only very recent that ideas from compressive sensing start being used in adaptive numerical solutions of PDEs.

Although compressive sensing is a new field, it has already reached a certain stage of maturity. Using its ideas and concepts in matrix rank minimization and numerical solution of operator equations, however, is currently still in its beginnings. The workshop aims at investigating interactions between the three focused areas and thereby stimulating new research.