Intersections and sums of sets for the regularization of inverse problems

We present new algorithms to compute projections onto the intersection of constraint sets. We focus on problems with multiple sets for which there is no simple and closed-form projection. Different from more classical methods such as Dykstra's algorithm, we do not need other algorithms to solve sub-problems. Our algorithms are based on the alternating direction method of multipliers and apply to models/images/video on small 2D and large 3D grids because we exploit computational similarity between constraint sets, coarse and fine-grained parallelism, and we also present a multilevel accelerated version. To obtain more flexible descriptions of prior knowledge, we introduce a formulation that allows constraint sets to be the sum of intersections of sets, which is essentially an extension of a Minkowski set. This formulation builds on the success of additive image descriptions that are usually based on penalty methods, such as cartoon-texture decomposition and robust principal component analysis. We show applications where we use multiple constraint sets to regularize partial-differential-equation based parameter estimation problems such as seismic waveform inversion, as well as various image and video processing and segmentation tasks.