FISTA

The fundamental class from which all FISTA algorithms are derived is FISTA, which supports problems of the form

\[\mathrm{argmin}_{\mathbf{x}} \; f(\mathbf{x}) + g(\mathbf{x}) \;\;,\]

where \(f, g\) are convex functions and \(f\) is smooth. All the updates are made in input domain.

Additional classes within the fista.fista module support less general forms of problem; this specialisation allows for a smaller number of methods that have to be overriden in derived classes.

Classes derived from FISTA should override/define the methods and attributes in the following sections.

Initialisation

The __init__ method of the derived class should call the FISTA __init__ method to ensure proper initialisation.

State variable \(\mathbf{x}\) is initialised to zero by FISTA.xinit. This method should be overridden if a different initialization is desired.

Update Steps

The FISTA updates steps are defined by the following methods:

  • FISTA.proximal_step

    Compute

    \[\mathbf{x}^{(j+1)} = \mathrm{prox}_{t}(g) \left( \mathbf{y}^{(j)} - \frac{1}{L}\; \nabla_{\mathbf{x}} f(\mathbf{y}^{(j)}) \right) \;,\]

    where the proximal operation is defined as:

    \[\mathrm{prox}_{t}(g)\left( \mathbf{x} \right) = \mathrm{argmin}_{\mathbf{u}} \;\; g(\mathbf{u}) + \frac{1}{2 t} \left\| \mathbf{u} - \mathbf{x} \right\|_2^2 \; .\]

    This method should set self.X as a function of self.Y and gradient of \(f\).

  • FISTA.combination_step

    Compute

    \[\mathbf{y}^{(j+1)} = \mathbf{x}^{(j+1)} + \frac{t^{(j)} - 1}{t^{(j+1)}} \left( \mathbf{x}^{(j+1)} - \mathbf{x}^{(j)} \right) \;,\]

    with

    \[t^{(j+1)} = \frac{1}{2} \left( 1 + \sqrt{1 + 4 \; (t^{(j)})^2} \right) \;,\]

    starting with \(t^{(1)} = 1\).

    This method should set self.Y as a function of self.X and self.Xprv.

  • FISTA.compute_backtracking

    The bactracking process is an adaptive process to find the optimal step size for the gradient descent (\(L^{-1}\)). Backtracking updates self.L until the condition \(F \leq Q_L\) is satisfied. These are defined as

    \[F(\mathbf{x}) = f(\mathbf{x}) + g(\mathbf{x}) \;,\]

    and

    \[Q_L(\mathbf{x},\mathbf{y}) = f(\mathbf{y}) + \langle \mathbf{x} - \mathbf{y}, \nabla f(\mathbf{y}) \rangle + \frac{L}{2} \left\| \mathbf{x} - \mathbf{y} \right\|_2^2 + g(\mathbf{x}) \;.\]

    The backtracking process is optional. It is performed when the BackTrack mechanism is enabled.

A derived class implementing a fully-specified FISTA problem (as opposed to a partial specialisation) must define FISTA.eval_proxop, FISTA.eval_grad and FISTA.eval_R. It is usually not necessary to override FISTA.compute_backtracking since it is defined in FISTA in terms of calls to FISTA.eval_grad, FISTA.eval_R and FISTA.proximal_step.

Residual Evaluation

The following methods support evaluation of the residuals:

  • FISTA.rsdl

    This method has to be defined according to the stopping criterion to use. (It could be the relative difference between consecutive \(\mathbf{x}\) iterates or a fixed point residual evaluating the difference between \(\mathbf{x}\) and \(\mathbf{y}\) states).

Iteration Statistics

There is a flexible but relatively complex mechanism supporting the recording of statistics such as objective function and residual values for each iteration.

IterationStats Definition

These statistics are recorded as a collections.namedtuple class, self.IterationStats. The fields of this namedtuple are defined by class method IterativeSolver.itstat_fields, which returns a tuple of fields consisting of the following components:

  • Iter : Iteration number
  • A tuple of field names in FISTA.itstat_fields_objfn : Fields representing the objective function and and its individual terms
  • Rsdl : Norm of residual
  • F_Btrack : Evaluation of \(F\) (if backtracking is enabled)
  • Q_Btrack : Evaluation of \(Q_L\) (if backtracking is enabled)
  • IterBTrack : Number of iterations used in backtracking (if backtracking is enabled)
  • L : Inverse of gradient step size.
  • A tuple of field names in FISTA.itstat_fields_extra : Optional extra fields
  • Time : Cumulative run time

In most cases a derived class will simply override FISTA.itstat_fields_objfn and FISTA.itstat_fields_extra to customise the desired iteration statistics fields, but if more flexibility is required, IterativeSolver.itstat_fields should be overridden.

IterationStats Construction

The actual construction of the self.IterationStats namedtuple for each iteration is performed by FISTA.iteration_stats, which expects that self.IterationStats follows the structure defined by IterativeSolver.itstat_fields. Tuples of values corresponding to the fields defined in FISTA.itstat_fields_objfn and FISTA.itstat_fields_extra should be returned by FISTA.eval_objfn and FISTA.itstat_extra respectively.

In FISTA, FISTA.itstat_fields_objfn is defined as the tuple ('ObjFun', 'FVal', 'GVal'), and FISTA.eval_objfn constructs the corresponding field values by calls to FISTA.obfn_f and FISTA.obfn_g, which are expected to return the values of \(f(\mathbf{x})\) and \(g(\mathbf{x})\) respectively. In the simplest case it is sufficient to just define FISTA.obfn_f and FISTA.obfn_g in a derived class, but in most cases one would instead override FISTA.itstat_fields_objfn and FISTA.eval_objfn (and possibly FISTA.itstat_fields_extra and FISTA.itstat_extra as well).

Status Display

When option Verbose is enabled, a summary of the iterations statistics is printed to the standard output. The printing of this summary is controlled by FISTA.display_start, FISTA.display_status, FISTA.display_end, and the state of the BackTrack flag. These methods will usually not need to be overridden since there is a flexible method of customising the information displayed by these methods.

Class method FISTA.hdrtxt returns a tuple of strings which will be displayed as the headings for the displayed columns of iteration statistics, and class method FISTA.hdrval constructs a dictionary that defines a mapping between these column heading strings and corresponding field names in the self.IterationStats namedtuple. These two methods can be overridden if necessary, but in most cases it is sufficient to override FISTA.hdrtxt_objfn and FISTA.hdrval_objfun, which respectively define the header strings and mappings for the statistics related to the objective function (see FISTA.itstat_fields_objfn and FISTA.eval_objfn in IterationStats Construction).