Frame-based image deblurring with unknown boundary conditions using the alternating direction method of multipliers

The alternating direction method of multipliers (ADMM) is an efficient optimization tool that achieves state-of-the-art speed in several imaging inverse problems, by splitting the underlying problem into simpler, efficiently solvable sub-problems. In deconvolution, one of these sub-problems requires a matrix inversion, which has been shown to be efficiently computable (via the FFT), if the observation operator is circulant, i.e., under periodic boundary conditions. We extend ADMM-based image deconvolution to a more realistic scenario: unknown boundaries. The observation is modeled as the composition of a periodic convolution with a spatial mask that excludes the regions where the periodic convolution is invalid. We show that the resulting algorithms inherit the convergence guarantees of ADMM and illustrate its performance on non-periodic de-blurring under frame-based regularization.