Optimization is playing an increasingly important role in computational imaging, where many problems reduce to large-scale optimization with structures. The huge number of variables in imaging problems often preclude the use of off-the-shelf, sophisticated algorithms such as the interior-point methods because they exceed memory limits. Scalable optimization algorithms with small memory footprints, low per-iteration costs, and excellent parallelization properties have become the popular choices. Algorithms for structure optimization have recently received significant improvements due to the revival of numerical techniques such as operator splitting, stochastic sampling, and coordinate update. Favorable structures in imaging problems can reduce a problem with a huge number of variables and data to simple, small, parallel subproblems. Developing and adapting such algorithms can potentially revolutionize the solution to many imaging problems. However, exploiting structures in large-scale optimization is not an easy task as one needs to recognize those structures to generate simple subproblems, and then combine them into fast and scalable algorithms. This is harder than applying ADMM or block coordinate descent right out of the box.
This tutorial focuses on latest first-order algorithms and the techniques of exploiting problem structures. It will provide a high-level overview of operator splitting and coordinate update methods (which include proximal, ADMM, primal-dual, and coordinate descent methods as special cases) in the context of computational imaging, along with concrete examples in image reconstruction, optical flow, segmentation, and others. Emphasis will be given to exploiting problem structures and the fundamental mechanism of building first-order algorithms with fast convergence. Some key results will be "proved" in simplified settings and through graphical illustrations. Stochastic approximating algorithms and recent nonconvex optimization results will also be included.