ABSTRACT
Image and signal processing problems of practical importance, such as incomplete
data recovery and compressed sensing, are often modeled as nonsmooth optimization
problems whose objective functions are the sum of two terms, each of which is the
composition of a prox-friendly function with a matrix. Therefore, there is a practical
need to solve such optimization problems. Besides the nondifferentiability of the
objective functions of the associated optimization problems and the larger dimension
of the underlying images and signals, the sum of the objective functions is not,
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
relies heavily on the underlying structures of the matrices, particularly for large scale
optimization problems. In this dissertation, we propose a novel algorithmic framework
that exploits the availability of the prox-friendly functions, without requiring
any structural information of the matrices. This makes our algorithms suitable for
large scale optimization problems of interest. We also prove the convergence of the
developed algorithms.
This dissertation has three main parts. In part 1, we consider the minimization
of functions that are the sum of the compositions of prox-friendly functions with
matrices. We characterize the solutions to the associated optimization problems as
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
provided by this characterization, we develop a block Gauss-Seidel iterative scheme
for finding a solution to the optimization problem and prove its convergence. We
discuss the connection of our developed algorithms with some existing ones and point
out the advantages of our proposed scheme.
In part 2, we give a comprehensive study on the computation of the proximity
operator of the ℓp-norm with 0 ≤ p < 1. Nonconvexity and non-smoothness have
been recognized as important features of many optimization problems in image and
signal processing. The nonconvex, nonsmooth ℓp-regularization has been recognized
as an efficient tool to identify the sparsity of wavelet coefficients of an image or signal
under investigation. To solve an ℓp-regularized optimization problem, the proximity
operator of the ℓp-norm needs to be computed in an accurate and computationally
efficient way. We first study the general properties of the proximity operator of the
ℓp-norm. Then, we derive the explicit form of the proximity operators of the ℓp-norm
for p ∈ {0, 1/2, 2/3, 1}. Using these explicit forms and the properties of the proximity
operator of the ℓp-norm, we develop an efficient algorithm to compute the proximity
operator of the ℓp-norm for any p between 0 and 1.
In part 3, the usefulness of the research results developed in the previous two
parts is demonstrated in two types of applications, namely, image restoration and
compressed sensing. A comparison with the results from some existing algorithms
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
peak signal-to-noise ratios and the developed algorithms require less CPU time than
state-of-the-art algorithms. In addition, for compressed sensing applications, our
algorithm has smaller ℓ2- and ℓ∞-errors and shorter computation times than state-ofthe-
art algorithms. For compressed sensing with the ℓp-regularization, our numerical
simulations show smaller ℓ2- and ℓ∞-errors than that from the ℓ0-regularization and
ℓ1-regularization. In summary, our numerical simulations indicate that not only can
our developed algorithms be applied to a wide variety of important optimization
problems, but also they are more accurate and computationally efficient than stateof-
the-art algorithms.
","abstract_html":"<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>","abstract_has_math":false,"creators":["Chen, Feishe"],"institution":null,"degree_name":"Doctor of Philosophy (PhD)","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Lixin Shen"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-12-01T08:00:00Z","date_published":"2015-12-01T08:00:00Z","updated_at":"2026-07-24T04:55:06Z","subjects":["Physical Sciences and Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://surface.syr.edu/etd/383","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Lixin Shen"]},{"key":"dc:creator","label":"Author","values":["Chen, Feishe"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Physical Sciences and Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://surface.syr.edu/etd/383"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["ABSTRACT
Image and signal processing problems of practical importance, such as incomplete
data recovery and compressed sensing, are often modeled as nonsmooth optimization
problems whose objective functions are the sum of two terms, each of which is the
composition of a prox-friendly function with a matrix. Therefore, there is a practical
need to solve such optimization problems. Besides the nondifferentiability of the
objective functions of the associated optimization problems and the larger dimension
of the underlying images and signals, the sum of the objective functions is not,
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
relies heavily on the underlying structures of the matrices, particularly for large scale
optimization problems. In this dissertation, we propose a novel algorithmic framework
that exploits the availability of the prox-friendly functions, without requiring
any structural information of the matrices. This makes our algorithms suitable for
large scale optimization problems of interest. We also prove the convergence of the
developed algorithms.
This dissertation has three main parts. In part 1, we consider the minimization
of functions that are the sum of the compositions of prox-friendly functions with
matrices. We characterize the solutions to the associated optimization problems as
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
provided by this characterization, we develop a block Gauss-Seidel iterative scheme
for finding a solution to the optimization problem and prove its convergence. We
discuss the connection of our developed algorithms with some existing ones and point
out the advantages of our proposed scheme.
In part 2, we give a comprehensive study on the computation of the proximity
operator of the ℓp-norm with 0 ≤ p < 1. Nonconvexity and non-smoothness have
been recognized as important features of many optimization problems in image and
signal processing. The nonconvex, nonsmooth ℓp-regularization has been recognized
as an efficient tool to identify the sparsity of wavelet coefficients of an image or signal
under investigation. To solve an ℓp-regularized optimization problem, the proximity
operator of the ℓp-norm needs to be computed in an accurate and computationally
efficient way. We first study the general properties of the proximity operator of the
ℓp-norm. Then, we derive the explicit form of the proximity operators of the ℓp-norm
for p ∈ {0, 1/2, 2/3, 1}. Using these explicit forms and the properties of the proximity
operator of the ℓp-norm, we develop an efficient algorithm to compute the proximity
operator of the ℓp-norm for any p between 0 and 1.
In part 3, the usefulness of the research results developed in the previous two
parts is demonstrated in two types of applications, namely, image restoration and
compressed sensing. A comparison with the results from some existing algorithms
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
peak signal-to-noise ratios and the developed algorithms require less CPU time than
state-of-the-art algorithms. In addition, for compressed sensing applications, our
algorithm has smaller ℓ2- and ℓ∞-errors and shorter computation times than state-ofthe-
art algorithms. For compressed sensing with the ℓp-regularization, our numerical
simulations show smaller ℓ2- and ℓ∞-errors than that from the ℓ0-regularization and
ℓ1-regularization. In summary, our numerical simulations indicate that not only can
our developed algorithms be applied to a wide variety of important optimization
problems, but also they are more accurate and computationally efficient than stateof-
the-art algorithms.
"]},{"key":"dc:title","label":"Title","values":["Composite Minimization: Proximity Algorithms and Their Applications"]}]}],"canonical_facts":{"dc:contributor":["Lixin Shen"],"dc:creator":["Chen, Feishe"],"dc:description.abstract":["ABSTRACT
Image and signal processing problems of practical importance, such as incomplete
data recovery and compressed sensing, are often modeled as nonsmooth optimization
problems whose objective functions are the sum of two terms, each of which is the
composition of a prox-friendly function with a matrix. Therefore, there is a practical
need to solve such optimization problems. Besides the nondifferentiability of the
objective functions of the associated optimization problems and the larger dimension
of the underlying images and signals, the sum of the objective functions is not,
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
relies heavily on the underlying structures of the matrices, particularly for large scale
optimization problems. In this dissertation, we propose a novel algorithmic framework
that exploits the availability of the prox-friendly functions, without requiring
any structural information of the matrices. This makes our algorithms suitable for
large scale optimization problems of interest. We also prove the convergence of the
developed algorithms.
This dissertation has three main parts. In part 1, we consider the minimization
of functions that are the sum of the compositions of prox-friendly functions with
matrices. We characterize the solutions to the associated optimization problems as
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
provided by this characterization, we develop a block Gauss-Seidel iterative scheme
for finding a solution to the optimization problem and prove its convergence. We
discuss the connection of our developed algorithms with some existing ones and point
out the advantages of our proposed scheme.
In part 2, we give a comprehensive study on the computation of the proximity
operator of the ℓp-norm with 0 ≤ p < 1. Nonconvexity and non-smoothness have
been recognized as important features of many optimization problems in image and
signal processing. The nonconvex, nonsmooth ℓp-regularization has been recognized
as an efficient tool to identify the sparsity of wavelet coefficients of an image or signal
under investigation. To solve an ℓp-regularized optimization problem, the proximity
operator of the ℓp-norm needs to be computed in an accurate and computationally
efficient way. We first study the general properties of the proximity operator of the
ℓp-norm. Then, we derive the explicit form of the proximity operators of the ℓp-norm
for p ∈ {0, 1/2, 2/3, 1}. Using these explicit forms and the properties of the proximity
operator of the ℓp-norm, we develop an efficient algorithm to compute the proximity
operator of the ℓp-norm for any p between 0 and 1.
In part 3, the usefulness of the research results developed in the previous two
parts is demonstrated in two types of applications, namely, image restoration and
compressed sensing. A comparison with the results from some existing algorithms
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
peak signal-to-noise ratios and the developed algorithms require less CPU time than
state-of-the-art algorithms. In addition, for compressed sensing applications, our
algorithm has smaller ℓ2- and ℓ∞-errors and shorter computation times than state-ofthe-
art algorithms. For compressed sensing with the ℓp-regularization, our numerical
simulations show smaller ℓ2- and ℓ∞-errors than that from the ℓ0-regularization and
ℓ1-regularization. In summary, our numerical simulations indicate that not only can
our developed algorithms be applied to a wide variety of important optimization
problems, but also they are more accurate and computationally efficient than stateof-
the-art algorithms.
"],"dc:identifier":["https://surface.syr.edu/etd/383"],"dc:subject":["Physical Sciences and Mathematics"],"dc:title":["Composite Minimization: Proximity Algorithms and Their Applications"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-24T04:55:06Z"}