7. Sparsity Based Nonlocal Image Restoration: An Alternating Optimization Approach

There are many rich connections between the theory of mathematical optimization and the practice of image restoration. However, several fundamental questions remain open—e.g., how to translate some physical insight into an appropriate mathematical objective/cost functional? what kind of optimization tools should be called on first? The objective of this chapter is to stress the difference between the theory and the practice—namely, in the practice of image restoration, the objective is often not to solve the formulated optimization problem correctly but to obtain a nicely-restored image through the process of optimization. In other words, we advocate the termination of an iterative optimization algorithm before it reaches the convergence for various practical considerations (e.g., computational constraints, regularization purpose). Meanwhile, we will show that strategies such as relaxation and divide-and-conquer—even though they do not help the pursuit of a globally optimal solution—are often sufficient for the applications of image restoration. We will use two specific applications—namely image denoising and compressed sensing—to demonstrate how simultaneous sparse coding and nonlocal regularization both admit a nonconvex optimization-based formulation, which can lead to novel insights to our understanding why BM3D and BM3D-CS can achieve excellent performance.