Gitta Kutyniok (joint work with David Donoho, Stanford University)

Title: l1-Minimization and the Geometric Separation Problem

Abstract: Modern data are often 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 have already been obtained.

In this talk we develop a theoretical approach to this Geometric Separation Problem in which a deliberately overcomplete representation is chosen made of two frames. One is suited to pointlike structures (wavelets) and the other suited to curvelike structures (curvelets or shearlets). The decomposition principle is to minimize the  $\ell_1$ norm of the analysis (rather than synthesis) frame coefficients. Our theoretical results show that at all sufficiently fine scales, nearly-perfect separation is indeed achieved.

Our analysis has three interesting features. Firstly, we use a viewpoint deriving from microlocal analysis to understand heuristically why separation might be possible and to organize a rigorous analysis. Secondly, we introduce some novel technical tools: cluster coherence, rather than the now-traditional singleton coherence and $\ell_1$-minimization in frame settings, including those where singleton coherence within one frame may be high. Thirdly, our approach to exploiting $\ell_1$ minimization by using the geometry of the problem as the driving force reaches conclusions reminiscent of those which have been obtained previously using randomness of the sparsity pattern to be recovered; however here, the pattern is not random but highly organized.