Proximal gradient method
Proximal gradient methods are a generalized form of projection used to solve non-differentiable convex optimization problems. Many interesting problems can be formulated as convex optimization problems of the form formula_1 where formula_2 are convex functions defined from formula_3 where some of the functions are non-differentiable. This rules out conventional smooth optimization techniques like Steepest descent method, conjugate gradient method etc. Proximal gradient methods can be used instead. These methods proceed by splitting, in that the functions formula_4 are used individually so as to yield an easily implementable algorithm. They are called proximal because each non  smooth function among formula_4 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. For the theory of proximal gradient methods from the perspective of and with applications to statistical learning theory, see proximal gradient methods for learning. Notations and terminology. Let formula_6, the formula_7-dimensional Euclidean space, be the domain of the function formula_8. Suppose formula_9 is a non-empty convex subset of formula_6. Then, the indicator function of formula_9 is defined as The distance from formula_16 to formula_9  is defined as If formula_9 is closed and convex, the projection of formula_16 onto formula_9 is the unique point formula_22 such that formula_23. The subdifferential of formula_24 at formula_25 is given by Projection onto convex sets (POCS). One of the widely used convex optimization algorithms is projections onto convex sets (POCS). This algorithm is employed to recover/synthesize a signal satisfying simultaneously several convex constraints. Let formula_27 be the indicator function of non-empty closed convex set formula_28 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 formula_28. In POCS method each set formula_28 is incorporated by its projection operator formula_31. So in each iteration formula_25 is updated as 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. The proximity operator of a convex function formula_24 at formula_25 is defined as the unique solution to and is denoted formula_37. Note that in the specific case where formula_24 is the indicator  function formula_40 of some convex set formula_9 showing that the proximity operator is indeed a generalisation of the projection operator. The proximity operator of formula_24 is characterized by inclusion If formula_24 is differentiable then above equation reduces to Examples. Special instances of Proximal Gradient Methods are