Sparsity, $\ell_1$ Minimization, and the Geometric Separation Problem

Sparsity, $\ell_1$ Minimization, and the Geometric Separation Problem

Thu, 15/10/2009
14:00 		Prof. Gitta Kutyniok (University of Osnabruck) Computational Mathematics and Applications Add to calendar 3WS SR
Sparsity, $ \ell_1 $ Minimization, and the Geometric Separation Problem
During the last two years, sparsity has become a key concept in various areas of applied mathematics, computer science, and electrical engineering. Sparsity methodologies explore the fundamental fact that many types of data/signals can be represented by only a few non-vanishing coefficients when choosing a suitable basis or, more generally, a frame. If signals possess such a sparse representation, they can in general be recovered from few measurements using $ \ell_1 $ minimization techniques. One application of this novel methodology is the geometric separation of data, which is composed of two (or more) geometrically distinct constituents – for instance, pointlike and curvelike structures in astronomical imaging of galaxies. Although it seems impossible to extract those components – as there are two unknowns for every datum – suggestive empirical results using sparsity considerations have already been obtained. In this talk we will first give an introduction into the concept of sparse representations and sparse recovery. Then we will develop a very general theoretical approach to the problem of geometric separation based on these methodologies by introducing novel ideas such as geometric clustering of coefficients. Finally, we will apply our results to the situation of separation of pointlike and curvelike structures in astronomical imaging of galaxies, where a deliberately overcomplete representation made of wavelets (suited to pointlike structures) and curvelets/shearlets (suited to curvelike structures) will be chosen. The decomposition principle is to minimize the $ \ell_1 $ norm of the frame coefficients. Our theoretical results, which are based on microlocal analysis considerations, show that at all sufficiently fine scales, nearly-perfect separation is indeed achieved. This is joint work with David Donoho (Stanford University).