Georgia Institute of Technology College of Sciences

Inpainting, deblurring and denoising images are common tasks required for a number of applications in science and engineering. Since the seminal work of Rudin, Osher and Fatemi, image regularization by total variation (TV) became a standard heuristic for achieving these tasks. In this talk, I will introduce the TV regularization model and some connections with sparse optimization and compressed sensing. Later, I will summarize some of the fastest existing methods for solving TV regularization. Motivated by improving the super-linear (on the dimension) running time of these algorithms, we propose two heuristics for image regularization models: the first one is to replace the TV by the \ell^1 norm of the Laplacian, and the second is a new, to the best of our knowledge, approximation of the TV seminorm, based on a redundant parameterization of the gradient field. We prove that the latter regularizer is an O(log n) approximation of the TV seminorm. This proof is based on basic techniques from Discrete Fourier Analysis and an estimate of the fundamental solutions of the Laplace equation on a grid, due to Mangad. Finally, we present preliminary computational results for the three models, on mid-scale images. This talk will be self-contained. Joint work with Arkadi Nemirovski.