sporco.fista.bpdn

Classes for FISTA algorithm for the BPDN problem

Classes

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.

Parameters:
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.
Parameters:
opt : dict or None, optional (default None)

BPDN algorithm options

setdict(D)[source]

Set dictionary array.

getcoef()[source]

Get final coefficient array.

eval_grad()[source]

Compute gradient in spatial domain for variable Y.

eval_proxop(V)[source]

Compute proximal operator of \(g\).

eval_R(V)[source]

Evaluate smooth term in V.

rsdl()[source]

Compute fixed point residual.

eval_objfn()[source]

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

obfn_reg()[source]

Compute regularisation term and contribution to objective function.

obfn_f(X=None)[source]

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

reconstruct(X=None)[source]

Reconstruct representation.