Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

L_1-Minimization and the Geometric Separation Problem

PDE and Applied Math Seminar

Speaker: Gitta Kutyniok, Stanford
Location: 1143 MSB
Start time: Thu, May 8 2008, 2:00PM

Consider an image mixing two (or more) geometrically distinct but spatially overlapping phenomena - for instance, pointlike and curvelike structures in astronomical imaging of galaxies. This raises the Problem of Geometric Separation, taking a single image and extracting two images one containing just the pointlike phenomena and one containing just the curvelike phenomena. Although this seems impossible - as there are two unknowns for every datum - suggestive empirical results have already been obtained. We develop a theoretical approach to the 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 L_1 norm of the analysis (rather than synthesis) frame coefficients. This forces the pointlike objects into the wavelet components of the expansion and the curvelike objects into the curvelet or shearlet part of the expansion. Our theoretical results show that at all sufficiently fine scales, nearly-perfect separation is achieved. Our analysis has two 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 L_1-minimization in frame settings, including those where singleton coherence within one frame may be high. Our general approach applies in particular to two variants of geometric separation algorithms. One is based on frames of radial wavelets and curvelets and the other uses orthonormal wavelets and shearlets. This is joint work with David Donoho (Stanford University)