Proximal gradient method

Convex optimization is a sub field of optimization which can produce reliable solutions and can be solved exactly. Many signal processing problems can be formulated as convex optimization problems of form

${\displaystyle {\begin{aligned}&\operatorname {minimize} _{x\in \mathbb {R} ^{N}}&&f_{1}(x)+f_{2}(x)+...+f_{n-1}(x)+f_{n}(x)\end{aligned}}}$

where ${\displaystyle f_{1},f_{2},...,f_{n}}$ are convex functions defined from ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} }$ where some of the functions are non-differentiable, this rules out our conventional smooth optimization techniques like Steepest decent method, conjugate gradient method etc. There is a specific class of algorithms which can solve above optimization problem. These methods proceed by splitting, in that the functions ${\displaystyle f_{1},...,f_{n}}$ are used individually so as to yield an easily implementable algorithm. They are called proximal because each non smooth function among ${\displaystyle f_{1},...,f_{n}}$ is involved via its proximity operator. Iterative Shrinkage thresholding algorithm, projected Landweber, projected gradient, alternating projections, alternating-direction method of multipliers, alternating split Bregman are special instances of proximal algorithms. Details of proximal methods are discussed in^[1]

Notations and Terminology

Let ${\displaystyle \mathbb {R} ^{N}}$ , the ${\displaystyle N}$ -dimensional euclidean space, be the ___domain of the function ${\displaystyle f:\mathbb {R} ^{N}\rightarrow [-\infty ,+\infty ]}$ . Suppose ${\displaystyle C}$  is the non-empty convex subset of ${\displaystyle \mathbb {R} ^{N}}$ . Then, the indicator function of ${\displaystyle C}$  is defined as

${\displaystyle i_{C}:x\mapsto \left\lbrace {\begin{aligned}&0&{\mbox{if }}x\in C\\&+\infty &{\mbox{if }}x\notin C\end{aligned}}\right.}$ 

${\displaystyle p}$ -norm is defined as ( ${\displaystyle \|.\|_{p}}$  )

${\displaystyle \|x\|_{p}=(|x_{1}|^{p}+|x_{2}|^{p}+\dots +|x_{N}|^{p})^{\frac {1}{p}}}$ 

The distance from ${\displaystyle x\in \mathbb {R} ^{N}}$  to ${\displaystyle C}$  is defined as

${\displaystyle D_{C}(x)=min_{y\in C}\|x-y\|}$ 

If ${\displaystyle C}$  is closed and convex, the projection of ${\displaystyle x\in \mathbb {R} ^{N}}$  onto ${\displaystyle C}$  is the unique point ${\displaystyle P_{C}x\in C}$  such that ${\displaystyle D_{C}(x)=\|x-P_{C}x\|_{2}}$ .

Subdifferential of ${\displaystyle f}$  is given by

${\displaystyle \partial f:\mathbb {R} ^{N}\rightarrow 2^{\mathbb {R} ^{N}}:x\mapsto \{u\in \mathbb {R} ^{N}|\forall y\in \mathbb {R} ^{N},(y-x)^{\mathrm {T} }u+f(x)\leq f(y))\}}$ 

Proximal Gradient methods

One of the widely used convex optimization algorithm is POCS (Projection Onto Convex Sets). This algorithm is employed to recover/synthesize a signal satisfying simultaneously several convex constraints. Let ${\displaystyle f_{i}}$  be the indicator function of non-empty closed convex set ${\displaystyle C_{i}}$  modeling a constraint. This reduces to convex feasibility problem, which require us to find a solution such that it lies in the intersection of all convex sets ${\displaystyle C_{i}}$ . In POCS method each set ${\displaystyle C_{i}}$  is incorporated by its projection operator ${\displaystyle P_{C_{i}}}$ . So in each iteration ${\displaystyle x}$  is updated as

${\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}...P_{C_{n}}x_{k}}$ 

However beyond such problems projection operators are not appropriate and more general operators are required to tackle them. Among the various generalizations of the notion of a convex projection operator that exist, proximity operators are best suited for other purposes.

Definition

Proximity operators of function ${\displaystyle f}$  at ${\displaystyle x}$  is defined as

For every ${\displaystyle x\in \mathbb {R} ^{N}}$ , the minimization problem,

${\displaystyle {\begin{aligned}&minimize_{y\in C}&f(y)+{\frac {1}{2}}\parallel x-y\parallel _{2}^{2}&\end{aligned}}}$  admits a unique solution which is denoted by ${\displaystyle prox_{f}(x)}$ .

${\displaystyle prox_{f}(x):\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{N}}$ 

The proximity operator of ${\displaystyle f}$  is characterized by inclusion

${\displaystyle {\begin{aligned}&p=prox_{f}(x)\Leftrightarrow x-p\in \partial f(p)&(\forall (x,p)\in \mathbb {R} ^{N}\times \mathbb {R} ^{N})\end{aligned}}}$ 

If ${\displaystyle f}$  is differentiable then above equation reduces to

${\displaystyle {\begin{aligned}&p=prox_{f}(x)\Leftrightarrow x-p\in \triangledown f(p)&(\forall (x,p)\in \mathbb {R} ^{N}\times \mathbb {R} ^{N})\end{aligned}}}$ 

Examples

Special instances of Proximal Gradient Methods are

• Basis Pursuit
• Projected Landweber
• Alternating Projection
• Alternating-direction method of multipliers
• Fast Iterative Shrinkage Thresholding Algorithm (FISTA)^[2]

See also

• Alternating Projection
• Convex Optimization
• Frank–Wolfe algorithm

References

• Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press.
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). Springer's Fixed-Point Algorithms for Inverse Problems in Science and Engineering. Vol. 49. pp. 185–212.

Notes

1. Combettes, Patrick L.; Pesquet, Jean-Chritophe (2009). "Proximal Splitting Methods in Signal Processing". p. {11–23}.
2. "Beck, A; Teboulle, M (2009). "A fast iterative shrinkage-thresholding algorithm for linear inverse problems". SIAM J. Imaging Science. Vol. 2. pp. 183–202.

External links

• Stephen Boyd and Lieven Vandenberghe Book , Convex optimization
• EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
• EE227A: Lieven Vandenberghe Notes Lecture 18