Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation

Computational harmonic analysis has a rich history spanning more than half a century, where the last decade has been strongly influenced by sparse regularisation and compressed sensing. The theory has matured over the last years, and it has become apparent that the success of compressed sensing in fields like magnetic resonance imaging (MRI), and imaging in general, is due to specific structures beyond just sparsity. Indeed, structured sampling and the structure of images represented in X-lets, for example, sparsity in levels, are key ingredients. The field relies on the crucial assumption that one can easily compute minimisers of convex optimisation problem. This assumption is false in general. One can typically easily compute the objective function of convex optimisation problems, but not minimisers. However, due to the specific features in compressed sensing, one can actually compute the desired minimisers fast and reliably to sufficient precision. In short, as we demonstrate here: the success of sparse regularisation and compressed sensing is due to specific key structures that allow for a beneficial interaction between harmonic analysis and optimisation.