Image data are often composed of two or more geometrically distinct constituents; in astronomical imaging of galaxies, for instance, one sees a mixture of pointlike structures (galaxy superclusters) and curvelike structures (filaments). It would be ideal to process a given image and create two separate images, where each one contains features from only one of the two geometric types. Recent empirical results show surprisingly good results are possible by minimizing the $ll_1$ norm of the coefficients in the combined representation by two separate overcomplete frames (wavelets and curvelets/shearlets) - although this may seem unlikely, as the linear equations involved are seriously underdetermined.

We present a theoretical analysis in a model problem showing that accurate geometric separation can be achieved by $ll_1$ minimization. We introduce the notions of cluster coherence and clustered sparse objects as a machinery to show that the underdetermined systems of equations can be stably solved by $ll_1$ minimization, and we develop microlocal analysis tools to perform the phase space calculations that cluster coherence requires. The idea that $ll_1$ minimization solves underdetermined problems when the important coefficients are clustered geometrically in phase space may have applications in other settings. Surprisingly, it will turn out that also the far simpler algorithm of one step of alternating block thresholding gives clean geometric separation in a model problem. This is joint work with David L. Donoho (Stanford University).