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.