Composite Minimization: Proximity Algorithms and Their Applications

<p>ABSTRACT</p> <p>Image and signal processing problems of practical importance, such as incomplete</p> <p>data recovery and compressed sensing, are often modeled as nonsmooth optimization</p> <p>problems whose objective functions are the sum of two terms, each of which is the</p> <p>composition of a prox-friendly function with a matrix. Therefore, there is a practical</p> <p>need to solve such optimization problems. Besides the nondifferentiability of the</p> <p>objective functions of the associated optimization problems and the larger dimension</p> <p>of the underlying images and signals, the sum of the objective functions is not,</p> <p>in general, prox-friendly, which makes solving the problems challenging. Many algorithms have been proposed in literature to attack these problems by making use of the prox-friendly functions in the problems. However, the efficiency of these algorithms</p> <p>relies heavily on the underlying structures of the matrices, particularly for large scale</p> <p>optimization problems. In this dissertation, we propose a novel algorithmic framework</p> <p>that exploits the availability of the prox-friendly functions, without requiring</p> <p>any structural information of the matrices. This makes our algorithms suitable for</p> <p>large scale optimization problems of interest. We also prove the convergence of the</p> <p>developed algorithms.</p> <p>This dissertation has three main parts. In part 1, we consider the minimization</p> <p>of functions that are the sum of the compositions of prox-friendly functions with</p> <p>matrices. We characterize the solutions to the associated optimization problems as</p> <p>the solutions of fixed point equations that are formulated in terms of the proximity operators of the dual of the prox-friendly functions. By making use of the flexibility</p> <p>provided by this characterization, we develop a block Gauss-Seidel iterative scheme</p> <p>for finding a solution to the optimization problem and prove its convergence. We</p> <p>discuss the connection of our developed algorithms with some existing ones and point</p> <p>out the advantages of our proposed scheme.</p> <p>In part 2, we give a comprehensive study on the computation of the proximity</p> <p>operator of the ℓp-norm with 0 ≤ p < 1. Nonconvexity and non-smoothness have</p> <p>been recognized as important features of many optimization problems in image and</p> <p>signal processing. The nonconvex, nonsmooth ℓp-regularization has been recognized</p> <p>as an efficient tool to identify the sparsity of wavelet coefficients of an image or signal</p> <p>under investigation. To solve an ℓp-regularized optimization problem, the proximity</p> <p>operator of the ℓp-norm needs to be computed in an accurate and computationally</p> <p>efficient way. We first study the general properties of the proximity operator of the</p> <p>ℓp-norm. Then, we derive the explicit form of the proximity operators of the ℓp-norm</p> <p>for p ∈ {0, 1/2, 2/3, 1}. Using these explicit forms and the properties of the proximity</p> <p>operator of the ℓp-norm, we develop an efficient algorithm to compute the proximity</p> <p>operator of the ℓp-norm for any p between 0 and 1.</p> <p>In part 3, the usefulness of the research results developed in the previous two</p> <p>parts is demonstrated in two types of applications, namely, image restoration and</p> <p>compressed sensing. A comparison with the results from some existing algorithms</p> <p>is also presented. For image restoration, the results developed in part 1 are applied to solve the ℓ2-TV and ℓ1-TV models. The resulting restored images have higher</p> <p>peak signal-to-noise ratios and the developed algorithms require less CPU time than</p> <p>state-of-the-art algorithms. In addition, for compressed sensing applications, our</p> <p>algorithm has smaller ℓ2- and ℓ∞-errors and shorter computation times than state-ofthe-</p> <p>art algorithms. For compressed sensing with the ℓp-regularization, our numerical</p> <p>simulations show smaller ℓ2- and ℓ∞-errors than that from the ℓ0-regularization and</p> <p>ℓ1-regularization. In summary, our numerical simulations indicate that not only can</p> <p>our developed algorithms be applied to a wide variety of important optimization</p> <p>problems, but also they are more accurate and computationally efficient than stateof-</p> <p>the-art algorithms.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Year

2015

Author dc:creator

• Chen, Feishe

Contributors dc:contributor

• Lixin Shen

• Physical Sciences and Mathematics

Repository record dc:identifier

https://surface.syr.edu/etd/383

OAI identifier oai:identifier

oai:surface.syr.edu:etd-1383