Classes for FISTA algorithm for the BPDN problem


BPDN(D, S[, lmbda, opt]) Base class for FISTA algorithm for the Basis Pursuit DeNoising (BPDN) [11] problem.

Class Descriptions

class sporco.fista.bpdn.BPDN(D, S, lmbda=None, opt=None)[source]

Bases: sporco.fista.fista.FISTA

Base class for FISTA algorithm for the Basis Pursuit DeNoising (BPDN) [11] problem.

Inheritance diagram of BPDN

The generic problem form is

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

where \(f = (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2\), and \(g(\cdot)\) is a penalty term or the indicator function of a constraint; with input image \(\mathbf{s}\), dictionary filters \(D\), and coefficient maps \(\mathbf{x}\). It is solved via the FISTA formulation

Proximal step

\[\mathbf{x}_k = \mathrm{prox}_{t_k}(g) (\mathbf{y}_k - 1/L \nabla f(\mathbf{y}_k) ) \;\;.\]

Combination step

\[\mathbf{y}_{k+1} = \mathbf{x}_k + \left( \frac{t_k - 1}{t_{k+1}} \right) (\mathbf{x}_k - \mathbf{x}_{k-1}) \;\;,\]

with \(t_{k+1} = \frac{1 + \sqrt{1 + 4 t_k^2}}{2}\).

After termination of the solve method, attribute itstat is a list of tuples representing statistics of each iteration. The fields of the named tuple IterationStats are:

Iter : Iteration number

ObjFun : Objective function value

DFid : Value of data fidelity term \((1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2\)

RegL1 : Value of regularisation term \(\lambda \| \mathbf{x} \|_1\)

Rsdl : Residual

L : Inverse of gradient step parameter

Time : Cumulative run time

This class supports an arbitrary number of spatial dimensions, dimN, with a default of 2. The input dictionary D is either dimN + 1 dimensional, in which case each spatial component (image in the default case) is assumed to consist of a single channel, or dimN + 2 dimensional, in which case the final dimension is assumed to contain the channels (e.g. colour channels in the case of images). The input signal set S is either dimN dimensional (no channels, only one signal), dimN + 1 dimensional (either multiple channels or multiple signals), or dimN + 2 dimensional (multiple channels and multiple signals). Determination of problem dimensions is handled by cnvrep.CSC_ConvRepIndexing.

D : array_like

Dictionary array

S : array_like

Signal array

lmbda : float

Regularisation parameter

opt : BPDN.Options object

Algorithm options

class Options(opt=None)[source]

Bases: sporco.fista.fista.Options

BPDN algorithm options

Options include all of those defined in fista.FISTA.Options, together with additional options:

L1Weight : An array of weights for the \(\ell_1\) norm. The array shape must be such that the array is compatible for multiplication with the X/Y variables. If this option is defined, the regularization term is \(\lambda \| \mathbf{w}_m \odot \mathbf{x} \|_1\) where \(\mathbf{w}\) denotes slices of the weighting array.
opt : dict or None, optional (default None)

BPDN algorithm options


Set dictionary array.


Get final coefficient array.


Compute gradient in spatial domain for variable Y.


Compute proximal operator of \(g\).


Evaluate smooth term in V.


Compute fixed point residual.


Compute components of objective function as well as total contribution to objective function.


Compute regularisation term and contribution to objective function.


Compute data fidelity term \((1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2\).


Reconstruct representation.