with parameter for functional .
A nice property of this operator is that minimizes the functional if and only if it is a fixed point of , i.e., .
As an example, let's derive the proximal operator for ,
To find the minimum of we differentiate element-wise with respect to and set the result equal to zero,
This corresponds to the following graph,
Either algebraically or graphically we may then obtain the following piecewise representation for in terms of ,
This corresponds to the element-wise soft-thresholding operator, , shown below.
The soft-thresholding operator may be written more compactly as
or in Deep-Learning notation as
Thus we have derived the proximal operator for the vector-norm to be the element-wise soft-thresholding operator (also known as the shrinkage-thresholding operator).
In order to continue our derivation of ISTA it is helpful for us to look at the proximal operator from a different perspective. First recall that the subdifferential of convex function at point is the set defined as
i.e., the set of slopes for which the hyperplanes at remain below the function. This allows us to generalize the idea of derivatives to convex functions that are non-smooth (not differentiable everywhere).
For instance, we know that a differentiable convex function has a global minimum at if and only if its gradient is zero, . Similarly this is the case for a non-smooth convex function if and only if zero is in the subdifferential, . Note that the subdifferential is equal to the gradient at a differentiable point.
is the global minimizer of as
Theorem: With some restrictions on convex function , the proximal operator is related to the subdifferential by
The inverse set-relation is referred to as the resolvent of the subdifferential.
Proof Boyd (3.4): Consider . Then,
Note that this shows that the set-relation for convex is single-valued, as the proximal operator is a single-valued function.
Armed with our understanding of the proximal operator, the subdifferential, and the prox-op's characterization as the resolvent of the subdifferential, we can continue on our journey to derive ISTA by deriving The Proximal Gradient Method (Boyd Sec 4.2.1).
First, we will state the method. Consider the following optimization problem:
with both convex functionals and differentiable. The proximal gradient method
is a fixed point iteration that converges to the unique minimizer of the objective function for a fixed step-size , where is the Lipschitz constant of . It can be shown that the algorithm converges as – very slow!
This can be seen from the necessary and sufficient condition that is a minimizer of if and only if zero is in its subdifferential,
We've used the fact that the proximal operator is the resolvent of the subdifferential to move from the containment relation to one of equality. The operator
is referred to as the forward-backward operator. The proximal gradient method as shown applies the forward-backward operator in a fixed-point iteration to minimize .
We're now ready to assemble the Iterative Soft-Thresholding Algorithm. We'll restate the objective for convenience,
where , i.e. a fat/over-complete dictionary, is our signal, and is our sparse code to be determined.
If we label the quadratic term as and the relaxed sparsity term as , we can use the proximal gradient method to get the update step
where is the proximal operator for the norm, soft-thresholding with parameter , as derived earlier.
More often, the ISTA update step is presented as
where , the square of the maximum singular value of , i.e. the largest eigen-value of and Lipschitz constant of . This is simply ISTA with its fixed maximum step-size, ensuring that in turn are contractive.
In sum, ISTA is a fixed-point iteration on the forward-backward operator defined by the soft-thresholding (prox-op of the norm) and the gradient of the quadratic difference between the original signal and its sparse-code reconstruction. The threshold and step-size of the algorithm are determined by the sparsity-fidelity trade-off required by the problem and the maximum scaling possible in the dictionary.