Algorithms and Applications for L1 Minimization

One of the most influential advances in image processing was the introduction of variational techniques, particularly those involving 11 regularization. For many problems in imaging, 11 regularization offers superior results when compared to other image processing techniques because of its edge preserving properties. Recently, the field of compressed sensing has reinvigorated research on 11 techniques. Compressed sensing allows high dimensional signals and images to be accurately reconstructed from a very small number of samples using 11 minimization. The effectiveness of 11 mines at a cost: because the 11 norm is non-differentiable and highly non-linear, variational techniques can be computationally costly. In this manuscript, we investigate fast, easy to use numerical methods for 11 regularized problems.;The first set of problems we consider are problems involving "vanilla" 11 regularization. Traditional techniques for this problem are either analogs of the gradient descent method, or are based on greedy algorithms. We consider two more efficient approaches: coordinate descent and conjugate gradient methods. It is conventionally considered impossible to efficiently apply coordinate descent to problems involving the Fourier transform. We present a technique for computing an iteration of coordinate descent more efficiently than the Fourier transform, making this technique effective for compressed sensing applications. We also consider a new conjugate gradient technique for 11 minimization. This technique is substantially faster than other conventional techniques, and can be shown to obtain exact minimizers in a finite number of steps.;We next consider problems involving total variation minimization. The split Bregman method is introduced, which is extremely effective for solving this problem. By using a splitting technique, split Bregman avoids the difficulties associated with most schemes for total variation minimization. A myriad of applications are explored including denoising, compressed sensing, segmentation, and surface reconstruction. The split Bregman method is compared to other algorithms, such as graph cuts, and is shown to offer superior performance.;Finally, we consider numerical schemes for computing global minimizers to non-convex problems. Many problems in images processing, including stereo matching and registration, can be formulated as non-convex minimization problems. Using a technique called functional lifting, it is often possible to find global minimizers for these problems. We present a general introduction to the concept of functional lifting. We then introduce a new technique which generalizes functional lifting to solve problems involving vector-valued functionals. This generalization will allow for the global minimization of classical optical flow image registration model.