We present primal-dual decomposition algorithms for convex optimization problems with cost functions $f(x) + g(Ax)$, where $f$ and $g$ have inexpensive proximal operators and $A$ can be decomposed as a sum of structured matrices. The methods are based on the Douglas-Rachford splitting algorithm applied to various splittings of the primal-dual optimality conditions. We discuss applications to image deblurring problems with non-quadratic data fidelity terms, different types of convex regularization, and simple convex constraints. In these applications, the primal-dual splitting approach allows us to handle general boundary conditions for the blurring operator. We also give a domain decomposition approach to image deblurring, where the blur operator may use a different blur kernel for each image patch, and at each iteration all patches are processed in parallel. Numerical results indicate that the primal-dual splitting methods compare favorably with the alternating direction method of multipliers, the Douglas-Rachford algorithm applied to a reformulated primal problem, and the Chambolle-Pock primal-dual algorithm.

A key property exploited in most image deblurring methods is spatial invariance of the blurring operator, which makes it possible to use the fast Fourier transform (FFT) when solving linear equations involving the operator. In this thesis we extend this approach to two popular models for space-varying blurring operators, the Nagy-O'Leary model and the Efficient Filter Flow model. We show how splitting methods derived from the Douglas-Rachford algorithm can be implemented with a low complexity per iteration, dominated by a small number of FFTs.