sporco.admm.cbpdn

Classes for ADMM algorithm for the Convolutional BPDN problem

Classes

GenericConvBPDN(*args, **kwargs)

Base class for ADMM algorithm for solving variants of the Convolutional BPDN (CBPDN) [49] [53] [51] problem.

ConvBPDN(*args, **kwargs)

ADMM algorithm for the Convolutional BPDN (CBPDN) [49] [53] [51] problem.

ConvBPDNJoint(*args, **kwargs)

ADMM algorithm for Convolutional BPDN with joint sparsity via an \(\ell_{2,1}\) norm term [51] (the \(\ell_2\) norms are computed over the channel index).

ConvElasticNet(*args, **kwargs)

ADMM algorithm for a convolutional form of the elastic net problem [64].

ConvBPDNGradReg(*args, **kwargs)

ADMM algorithm for an extension of Convolutional BPDN including a term penalising the gradient of the coefficient maps [52].

ConvBPDNProjL1(*args, **kwargs)

ADMM algorithm for a ConvBPDN variant with projection onto the \(\ell_1\) ball instead of an \(\ell_1\) penalty.

ConvTwoBlockCnstrnt(*args, **kwargs)

Base class for ADMM algorithms for problems of the form

ConvMinL1InL2Ball(*args, **kwargs)

ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint, following the general approach proposed in [2].

ConvBPDNMaskDcpl(*args, **kwargs)

ADMM algorithm for Convolutional BPDN with Mask Decoupling [28].

AddMaskSim(cbpdnclass, D, S, W, *args, **kwargs)

Boundary masking for convolutional representations using the Additive Mask Simulation (AMS) technique described in [50].

ConvL1L1Grd(*args, **kwargs)

ADMM algorithm for a Convolutional Sparse Coding problem with an \(\ell_1\) data fidelity term and both \(\ell_1\) and \(\ell_2\) of gradient regularisation terms [52].

MultiDictConvBPDN(cbpdnclass, D, S, *args, ...)

Solve a convolutional sparse coding problem fitting a single set of coefficient maps to multiple dictionaries and signals, e.g.


Class Descriptions

class sporco.admm.cbpdn.GenericConvBPDN(*args, **kwargs)[source]

Bases: sporco.admm.admm.ADMMEqual

Base class for ADMM algorithm for solving variants of the Convolutional BPDN (CBPDN) [49] [53] [51] problem.


Inheritance diagram of GenericConvBPDN


The generic problem form is

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + g( \{ \mathbf{x}_m \} )\]

for input image \(\mathbf{s}\), dictionary filters \(\mathbf{d}_m\), and coefficient maps \(\mathbf{x}_m\), and where \(g(\cdot)\) is a penalty term or the indicator function of a constraint. It is solved via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x}, \mathbf{y}} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + g( \{ \mathbf{y}_m \} ) \quad \text{such that} \quad \mathbf{x}_m = \mathbf{y}_m \;\;.\]

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) \| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \|_2^2\)

Reg : Value of regularisation term

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

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
Darray_like

Dictionary array

Sarray_like

Signal array

optGenericConvBPDN.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial/temporal dimensions

class Options(opt=None)[source]

Bases: sporco.admm.admm.ADMMEqual.Options

GenericConvBPDN algorithm options

Options include all of those defined in admm.ADMMEqual.Options, together with additional options:

AuxVarObj : Flag indicating whether the objective function should be evaluated using variable X (False) or Y (True) as its argument. Setting this flag to True often gives a better estimate of the objective function, but at additional computational cost.

LinSolveCheck : Flag indicating whether to compute relative residual of X step solver.

HighMemSolve : Flag indicating whether to use a slightly faster algorithm at the expense of higher memory usage.

NonNegCoef : Flag indicating whether to force solution to be non-negative.

NoBndryCross : Flag indicating whether all solution coefficients corresponding to filters crossing the image boundary should be forced to zero.

Parameters
optdict or None, optional (default None)

GenericConvBPDN algorithm options

setdict(D=None)[source]

Set dictionary array.

getcoef()[source]

Get final coefficient array.

xstep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{x}\).

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\). If this method is not overridden, the problem is solved without any regularisation other than the option enforcement of non-negativity of the solution and filter boundary crossing supression. When it is overridden, it should be explicitly called at the end of the overriding method.

obfn_fvarf()[source]

Variable to be evaluated in computing data fidelity term, depending on fEvalX option value.

eval_objfn()[source]

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

obfn_dfd()[source]

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

obfn_reg()[source]

Compute regularisation term(s) and contribution to objective function.

itstat_extra()[source]

Non-standard entries for the iteration stats record tuple.

rhochange()[source]

Updated cached c array when rho changes.

reconstruct(X=None)[source]

Reconstruct representation.

class sporco.admm.cbpdn.ConvBPDN(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.GenericConvBPDN

ADMM algorithm for the Convolutional BPDN (CBPDN) [49] [53] [51] problem.


Inheritance diagram of ConvBPDN


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{x}_m \|_1\]

for input image \(\mathbf{s}\), dictionary filters \(\mathbf{d}_m\), and coefficient maps \(\mathbf{x}_m\), via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x}, \mathbf{y}} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{y}_m \|_1 \quad \text{such that} \quad \mathbf{x}_m = \mathbf{y}_m \;\;.\]

Multi-image and multi-channel problems are also supported. The multi-image problem is

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \sum_k \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{k,m} - \mathbf{s}_k \right\|_2^2 + \lambda \sum_k \sum_m \| \mathbf{x}_{k,m} \|_1\]

with input images \(\mathbf{s}_k\) and coefficient maps \(\mathbf{x}_{k,m}\), and the multi-channel problem with input image channels \(\mathbf{s}_c\) is either

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \sum_c \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{c,m} - \mathbf{s}_c \right\|_2^2 + \lambda \sum_c \sum_m \| \mathbf{x}_{c,m} \|_1\]

with single-channel dictionary filters \(\mathbf{d}_m\) and multi-channel coefficient maps \(\mathbf{x}_{c,m}\), or

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \sum_c \left\| \sum_m \mathbf{d}_{c,m} * \mathbf{x}_m - \mathbf{s}_c \right\|_2^2 + \lambda \sum_m \| \mathbf{x}_m \|_1\]

with multi-channel dictionary filters \(\mathbf{d}_{c,m}\) and single-channel coefficient maps \(\mathbf{x}_m\).

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) \| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \|_2^2\)

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

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

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.


Call graph

../_images/cbpdn_init.svg

Parameters
Darray_like

Dictionary array

Sarray_like

Signal array

lmbdafloat

Regularisation parameter

optConvBPDN.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial/temporal dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.GenericConvBPDN.Options

ConvBPDN algorithm options

Options include all of those defined in admm.ADMMEqual.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 (see cnvrep.l1Wshape for more details). If this option is defined, the regularization term is \(\lambda \sum_m \| \mathbf{w}_m \odot \mathbf{x}_m \|_1\) where \(\mathbf{w}_m\) denotes slices of the weighting array on the filter index axis.

Parameters
optdict or None, optional (default None)

ConvBPDN algorithm options

uinit(ushape)[source]

Return initialiser for working variable U

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

obfn_reg()[source]

Compute regularisation term and contribution to objective function.

solve()

Call graph

../_images/cbpdn_solve.svg
class sporco.admm.cbpdn.ConvBPDNJoint(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

ADMM algorithm for Convolutional BPDN with joint sparsity via an \(\ell_{2,1}\) norm term [51] (the \(\ell_2\) norms are computed over the channel index).


Inheritance diagram of ConvBPDNJoint


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \sum_c \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{c,m} - \mathbf{s}_c \right\|_2^2 + \lambda \sum_c \sum_m \| \mathbf{x}_{c,m} \|_1 + \mu \| \{ \mathbf{x}_{c,m} \} \|_{2,1}\]

with input images \(\mathbf{s}_c\), dictionary filters \(\mathbf{d}_m\), and coefficient maps \(\mathbf{x}_{c,m}\), via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x}, \mathbf{y}} \; (1/2) \sum_c \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{c,m} - \mathbf{s}_c \right\|_2^2 + \lambda \sum_c \sum_m \| \mathbf{y}_{c,m} \|_1 + \mu \| \{ \mathbf{y}_{c,m} \} \|_{2,1} \quad \text{such that} \quad \mathbf{x}_{c,m} = \mathbf{y}_{c,m} \;\;.\]

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) \sum_c \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{k,m} - \mathbf{s}_c \right\|_2^2\)

RegL1 : Value of regularisation term \(\sum_c \sum_m \| \mathbf{x}_{c,m} \|_1\)

RegL21 : Value of regularisation term \(\| \{ \mathbf{x}_{c,m} \} \|_{2,1}\)

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual Residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

Time : Cumulative run time


Call graph

../_images/cbpdnjnt_init.svg

Parameters
Darray_like

Dictionary array

Sarray_like

Signal array

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (l2,1)

optConvBPDNJoint.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.ConvBPDN.Options

ConvBPDNJoint algorithm options

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

L21Weight : An array of weights for the \(\ell_{2,1}\) norm. The array shape must be such that the array is compatible for multiplication with the X/Y variables after the sum over axisC performed during the computation of the \(\ell_{2,1}\) norm. If this option is defined, the regularization term is \(\mu \sum_i w_i \sqrt{ \sum_c \mathbf{x}_{i,c}^2 }\) where \(w_i\) are the elements of the weight array, subscript \(c\) indexes the channel axis and subscript \(i\) indexes all other axes.

Parameters
optdict or None, optional (default None)

ConvBPDNJoint algorithm options

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

obfn_reg()[source]

Compute regularisation terms and contribution to objective function. Regularisation terms are \(\| Y \|_1\) and \(\| Y \|_{2,1}\).

solve()

Call graph

../_images/cbpdnjnt_solve.svg
class sporco.admm.cbpdn.ConvElasticNet(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

ADMM algorithm for a convolutional form of the elastic net problem [64].


Inheritance diagram of ConvElasticNet


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{x}_m \|_1 + (\mu/2) \sum_m \| \mathbf{x}_m \|_2^2\]

via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x}, \mathbf{y}} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{y}_m \|_1 + (\mu/2) \sum_m \| \mathbf{x}_m \|_2^2 \quad \text{such that} \quad \mathbf{x}_m = \mathbf{y}_m \;\;.\]

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) \| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \|_2^2\)

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

RegL2 : Value of regularisation term \((1/2) \sum_m \| \mathbf{x}_m \|_2^2\)

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

Time : Cumulative run time


Call graph

../_images/celnet_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (l2)

optConvBPDN.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

setdict(D=None)[source]

Set dictionary array.

xstep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{x}\).

obfn_reg()[source]

Compute regularisation term and contribution to objective function.

solve()

Call graph

../_images/cbpdnjnt_solve.svg
class sporco.admm.cbpdn.ConvBPDNGradReg(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

ADMM algorithm for an extension of Convolutional BPDN including a term penalising the gradient of the coefficient maps [52].


Inheritance diagram of ConvBPDNGradReg


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{x}_m \|_1 + (\mu/2) \sum_i \sum_m \| G_i \mathbf{x}_m \|_2^2 \;\;,\]

where \(G_i\) is an operator computing the derivative along index \(i\), via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x},\mathbf{y}} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \lambda \sum_m \| \mathbf{y}_m \|_1 + (\mu/2) \sum_i \sum_m \| G_i \mathbf{x}_m \|_2^2 \quad \text{such that} \quad \mathbf{x}_m = \mathbf{y}_m \;\;.\]

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) \| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \|_2^2\)

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

RegGrad : Value of regularisation term \((1/2) \sum_i \sum_m \| G_i \mathbf{x}_m \|_2^2\)

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

Time : Cumulative run time


Call graph

../_images/cbpdngrd_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (gradient)

optConvBPDNGradReg.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.ConvBPDN.Options

ConvBPDNGradReg algorithm options

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

GradWeight : An array of weights \(w_m\) for the term penalising the gradient of the coefficient maps. If this option is defined, the gradient regularization term is \(\sum_i \sum_m w_m \| G_i \mathbf{x}_m \|_2^2\) where \(w_m\) is the weight for filter index \(m\). The array should be an \(M\)-vector where \(M\) is the number of filters in the dictionary.

Parameters
optdict or None, optional (default None)

ConvBPDNGradReg algorithm options

setdict(D=None)[source]

Set dictionary array.

xstep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{x}\).

obfn_reg()[source]

Compute regularisation term and contribution to objective function.

solve()

Call graph

../_images/cbpdngrd_solve.svg
class sporco.admm.cbpdn.ConvBPDNProjL1(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.GenericConvBPDN

ADMM algorithm for a ConvBPDN variant with projection onto the \(\ell_1\) ball instead of an \(\ell_1\) penalty.


Inheritance diagram of ConvBPDNProjL1


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 \; \text{such that} \; \sum_m \| \mathbf{x}_m \|_1 \leq \gamma\]

via the ADMM problem

\[\mathrm{argmin}_{\mathbf{x}, \mathbf{y}} \; (1/2) \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2^2 + \iota_{C(\gamma)} (\{\mathbf{y}_m\}) \quad \text{such that} \quad \mathbf{x}_m = \mathbf{y}_m \;\;,\]

where \(\iota_{C(\gamma)}(\cdot)\) is the indicator function of the \(\ell_1\) ball of radius \(\gamma\) about the origin. The algorithm is very similar to that for the CBPDN problem (see ConvBPDN), the only difference being in the replacement in the \(\mathbf{y}\) step of the proximal operator of the \(\ell_1\) norm with the projection operator of the \(\ell_1\) norm. In particular, the \(\mathbf{x}\) step uses the solver from [49] for single-channel dictionaries, and the solver from [51] for multi-channel dictionaries.

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

Cnstr : Constraint violation measure

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

Time : Cumulative run time


Call graph

../_images/cbpdnprjl1_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

gammafloat

Constraint parameter

optConvBPDNProjL1.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.GenericConvBPDN.Options

ConvBPDNProjL1 algorithm options

Options are the same as those defined in GenericConvBPDN.Options.

Parameters
optdict or None, optional (default None)

ConvBPDNProjL1 algorithm options

uinit(ushape)[source]

Return initialiser for working variable U.

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

eval_objfn()[source]

Compute components of regularisation function as well as total objective function.

solve()

Call graph

../_images/cbpdnprjl1_solve.svg
class sporco.admm.cbpdn.ConvTwoBlockCnstrnt(*args, **kwargs)[source]

Bases: sporco.admm.admm.ADMMTwoBlockCnstrnt

Base class for ADMM algorithms for problems of the form

\[\mathrm{argmin}_\mathbf{x} \; g_0(D \mathbf{x} - \mathbf{s}) + g_1(\mathbf{x}) \;\;,\]

where \(D \mathbf{x} = \sum_m \mathbf{d}_m * \mathbf{x}_m\).


Inheritance diagram of ConvTwoBlockCnstrnt


The problem is solved via an ADMM problem of the form

\[\begin{split}\mathrm{argmin}_{\mathbf{x},\mathbf{y}_0,\mathbf{y}_1} \; g_0(\mathbf{y}_0) + g_1(\mathbf{y}_1) \;\text{such that}\; \left( \begin{array}{c} D \\ I \end{array} \right) \mathbf{x} - \left( \begin{array}{c} \mathbf{y}_0 \\ \mathbf{y}_1 \end{array} \right) = \left( \begin{array}{c} \mathbf{s} \\ \mathbf{0} \end{array} \right) \;\;.\end{split}\]

In this case the ADMM constraint is \(A\mathbf{x} + B\mathbf{y} = \mathbf{c}\) where

\[\begin{split}A = \left( \begin{array}{c} D \\ I \end{array} \right) \qquad B = -I \qquad \mathbf{y} = \left( \begin{array}{c} \mathbf{y}_0 \\ \mathbf{y}_1 \end{array} \right) \qquad \mathbf{c} = \left( \begin{array}{c} \mathbf{s} \\ \mathbf{0} \end{array} \right) \;\;.\end{split}\]

The implementation of this class is substantially complicated by the support of multi-channel signals. In the following, the number of channels in the signal and dictionary are denoted by C and Cd respectively, the number of signals and the number of filters are denoted by K and M respectively, D, X, and S denote the dictionary, coefficient map, and signal arrays respectively, and Y0 and Y1 denote blocks 0 and 1 of the auxiliary (split) variable of the ADMM problem. We need to consider three different cases:

  1. Single channel signal and dictionary (C = Cd = 1)

  2. Multi-channel signal, single channel dictionary (C > 1, Cd = 1)

  3. Multi-channel signal and dictionary (C = Cd > 1)

The final three (non-spatial) dimensions of the main variables in each of these cases are as in the following table:

Var.

C = Cd = 1

C > 1, Cd = 1

C = Cd > 1

D

1 x 1 x M

1 x 1 x M

Cd x 1 x M

X

1 x K x M

C x K x M

1 x K x M

S

1 x K x 1

C x K x 1

C x K x 1

Y0

1 x K x 1

C x K x 1

C x K x 1

Y1

1 x K x M

C x K x M

1 x K x M

In order to combine the block components Y0 and Y1 of variable Y into a single array, we need to be able to concatenate the two component arrays on one of the axes. The final M axis is suitable in the first two cases, but it is not possible to concatenate Y0 and Y1 on the final axis in case 3. The solution is that, in case 3, the the C and M axes of Y0 are swapped before concatenating, as well as after extracting the Y0 component from the concatenated Y variable (see block_sep0 and block_cat).


This class specialises class ADMMTwoBlockCnstrnt, but remains a base class for other classes that specialise to specific optimisation problems.

Parameters
Darray_like

Dictionary array

Sarray_like

Signal array

optConvTwoBlockCnstrnt.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.admm.ADMMTwoBlockCnstrnt.Options

ConvTwoBlockCnstrnt algorithm options

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

LinSolveCheck : Flag indicating whether to compute relative residual of X step solver.

HighMemSolve : Flag indicating whether to use a slightly faster algorithm at the expense of higher memory usage.

NonNegCoef : Flag indicating whether to force solution to be non-negative.

NoBndryCross : Flag indicating whether all solution coefficients corresponding to filters crossing the image boundary should be forced to zero.

Parameters
optdict or None, optional (default None)

ConvTwoBlockCnstrnt algorithm options

setdict(D=None)[source]

Set dictionary array.

getcoef()[source]

Get final coefficient array.

xstep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{x}\).

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

relax_AX()[source]

Implement relaxation if option RelaxParam != 1.0.

block_sep0(Y)[source]

Separate variable into component corresponding to \(\mathbf{y}_0\) in \(\mathbf{y}\;\;\). The method from parent class ADMMTwoBlockCnstrnt is overridden here to allow swapping of C (channel) and M (filter) axes in block 0 so that it can be concatenated on axis M with block 1. This is necessary because block 0 has the dimensions of S (N x C x K x 1) while block 1 has the dimensions of X (N x 1 x K x M).

block_cat(Y0, Y1)[source]

Concatenate components corresponding to \(\mathbf{y}_0\) and \(\mathbf{y}_1\) to form \(\mathbf{y}\;\;\). The method from parent class ADMMTwoBlockCnstrnt is overridden here to allow swapping of C (channel) and M (filter) axes in block 0 so that it can be concatenated on axis M with block 1. This is necessary because block 0 has the dimensions of S (N x C x K x 1) while block 1 has the dimensions of X (N x 1 x K x M).

cnst_A(X, Xf=None)[source]

Compute \(A \mathbf{x}\) component of ADMM problem constraint.

obfn_g0var()[source]

Variable to be evaluated in computing ADMMTwoBlockCnstrnt.obfn_g0, depending on the AuxVarObj option value.

cnst_A0(X, Xf=None)[source]

Compute \(A_0 \mathbf{x}\) component of ADMM problem constraint.

cnst_A0T(Y0)[source]

Compute \(A_0^T \mathbf{y}_0\) component of \(A^T \mathbf{y}\) (see ADMMTwoBlockCnstrnt.cnst_AT).

cnst_c0()[source]

Compute constant component \(\mathbf{c}_0\) of \(\mathbf{c}\) in the ADMM problem constraint.

eval_objfn()[source]

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

itstat_extra()[source]

Non-standard entries for the iteration stats record tuple.

reconstruct(X=None)[source]

Reconstruct representation.

rsdl_s(Yprev, Y)[source]

Compute dual residual vector.

rsdl_sn(U)[source]

Compute dual residual normalisation term.

class sporco.admm.cbpdn.ConvMinL1InL2Ball(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvTwoBlockCnstrnt

ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint, following the general approach proposed in [2].


Inheritance diagram of ConvMinL1InL2Ball


The \(\mathbf{y}\) step is essentially the same as that of admm.bpdn.MinL1InL2Ball (with the trivial difference of a swap between the roles of \(\mathbf{y}_0\) and \(\mathbf{y}_1\)). The \(\mathbf{x}\) step uses the solver from [49] for single-channel dictionaries, and the solver from [51] for multi-channel dictionaries.

Solve the Single Measurement Vector (SMV) problem

\[\mathrm{argmin}_\mathbf{x} \sum_m \| \mathbf{x}_m \|_1 \; \text{such that} \; \left\| \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right\|_2 \leq \epsilon\]

via the ADMM problem

\[\begin{split}\mathrm{argmin}_{\mathbf{x},\mathbf{y}_0,\mathbf{y}_1} \; \| \mathbf{y}_1 \|_1 + \iota_{C(\epsilon)}(\mathbf{y}_0) \;\text{such that}\; \left( \begin{array}{c} D \\ I \end{array} \right) \mathbf{x} - \left( \begin{array}{c} \mathbf{y}_0 \\ \mathbf{y}_1 \end{array} \right) = \left( \begin{array}{c} \mathbf{s} \\ \mathbf{0} \end{array} \right) \;\;,\end{split}\]

where \(\iota_{C(\epsilon)}(\cdot)\) is the indicator function of the \(\ell_2\) ball of radius \(\epsilon\) about the origin, and \(D \mathbf{x} = \sum_m \mathbf{d}_m * \mathbf{x}_m\). The Multiple Measurement Vector (MMV) problem

\[\mathrm{argmin}_\mathbf{x} \sum_k \sum_m \| \mathbf{x}_{k,m} \|_1 \; \text{such that} \; \left\| \sum_m \mathbf{d}_m * \mathbf{x}_{k,m} - \mathbf{s}_k \right\|_2 \leq \epsilon \;\;\; \forall k \;\;,\]

is also supported.

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 \(\| \mathbf{x} \|_1\)

Cnstr : Constraint violation measure

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

Time : Cumulative run time


Call graph

../_images/cbpdnml1l2_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

epsilonfloat

\(\ell_2\) ball radius

optConvMinL1InL2Ball.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.ConvTwoBlockCnstrnt.Options

ConvMinL1InL2Ball algorithm options

Options include all of those defined in ConvTwoBlockCnstrnt.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 (see cnvrep.l1Wshape for more details). If this option is defined, the objective function is \(\lambda \| \mathbf{w} \odot \mathbf{x} \|_1\) where \(\mathbf{w}\) denotes the weighting array.

NonNegCoef : If True, force solution to be non-negative.

Parameters
optdict or None, optional (default None)

ConvMinL1InL2Ball algorithm options

uinit(ushape)[source]

Return initialiser for working variable U.

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

obfn_g0(Y0)[source]

Compute \(g_0(\mathbf{y}_0)\) component of ADMM objective function.

obfn_g1(Y1)[source]

Compute \(g_1(\mathbf{y_1})\) component of ADMM objective function.

eval_objfn()[source]

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

solve()

Call graph

../_images/cbpdnml1l2_solve.svg
class sporco.admm.cbpdn.ConvBPDNMaskDcpl(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvTwoBlockCnstrnt

ADMM algorithm for Convolutional BPDN with Mask Decoupling [28].


Inheritance diagram of ConvBPDNMaskDcpl


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| W \left(\sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s}\right) \right\|_2^2 + \lambda \sum_m \| \mathbf{x}_m \|_1 \;\;,\]

where \(W\) is a mask array, via the ADMM problem

\[\begin{split}\mathrm{argmin}_{\mathbf{x},\mathbf{y}_0,\mathbf{y}_1} \; (1/2) \| W \mathbf{y}_0 \|_2^2 + \lambda \| \mathbf{y}_1 \|_1 \;\text{such that}\; \left( \begin{array}{c} D \\ I \end{array} \right) \mathbf{x} - \left( \begin{array}{c} \mathbf{y}_0 \\ \mathbf{y}_1 \end{array} \right) = \left( \begin{array}{c} \mathbf{s} \\ \mathbf{0} \end{array} \right) \;\;,\end{split}\]

where \(D \mathbf{x} = \sum_m \mathbf{d}_m * \mathbf{x}_m\).

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) \| W (\sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s}) \|_2^2\)

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

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

Time : Cumulative run time


Call graph

../_images/cbpdnmd_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

lmbdafloat

Regularisation parameter

Warray_like

Mask array. The array shape must be such that the array is compatible for multiplication with the internal shape of input array S (see cnvrep.CSC_ConvRepIndexing for a discussion of the distinction between external and internal data layouts) after reshaping to the shape determined by cnvrep.mskWshape.

optConvBPDNMaskDcpl.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.ConvTwoBlockCnstrnt.Options

ConvBPDNMaskDcpl algorithm options

Options include all of those defined in ConvTwoBlockCnstrnt.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 variable (see cnvrep.l1Wshape for more details). If this option is defined, the regularization term is \(\lambda \sum_m \| \mathbf{w}_m \odot \mathbf{x}_m \|_1\) where \(\mathbf{w}_m\) denotes slices of the weighting array on the filter index axis.

Parameters
optdict or None, optional (default None)

ConvBPDNMaskDcpl algorithm options

uinit(ushape)[source]

Return initialiser for working variable U.

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

eval_objfn()[source]

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

obfn_g0(Y0)[source]

Compute \(g_0(\mathbf{y}_0)\) component of ADMM objective function.

obfn_g1(Y1)[source]

Compute \(g_1(\mathbf{y_1})\) component of ADMM objective function.

solve()

Call graph

../_images/cbpdnmd_solve.svg
class sporco.admm.cbpdn.AddMaskSim(cbpdnclass, D, S, W, *args, **kwargs)[source]

Bases: object

Boundary masking for convolutional representations using the Additive Mask Simulation (AMS) technique described in [50]. Implemented as a wrapper about a cbpdn.ConvBPDN or derived object (or any other object with sufficiently similar interface and internals). The wrapper is largely transparent, but must be taken into account when setting some of the options for the inner object, e.g. the shape of the L1Weight option array must take into account the extra dictionary atom appended by the wrapper.

Parameters
cbpdnclassclass name

Type of internal cbpdn object (e.g. cbpdn.ConvBPDN) to be constructed

Darray_like

Dictionary array

Sarray_like

Signal array

Warray_like

Mask array. The array shape must be such that the array is compatible for multiplication with input array S (see cnvrep.mskWshape for more details).

*args

Variable length list of arguments for constructor of internal cbpdn object

**kwargs

Keyword arguments for constructor of internal cbpdn object

ystep()[source]

This method is inserted into the inner cbpdn object, replacing its own ystep method, thereby providing a hook for applying the additional steps necessary for the AMS method.

obfn_gvar()[source]

This method is inserted into the inner cbpdn object, replacing its own obfn_gvar method, thereby providing a hook for applying the additional steps necessary for the AMS method.

solve()[source]

Call the solve method of the inner cbpdn object and strip the AMS component from the returned result.

setdict(D=None)[source]

Set dictionary array.

getcoef()[source]

Get result of inner cbpdn object with AMS component removed.

index_primary()[source]

Return an index expression appropriate for extracting the primary (inner) component of the main variables X, Y, etc.

index_addmsk()[source]

Return an index expression appropriate for extracting the additive mask (outer) component of the main variables X, Y, etc.

reconstruct(X=None)[source]

Reconstruct representation.

getitstat()[source]

Get iteration stats from inner cbpdn object.

class sporco.admm.cbpdn.ConvL1L1Grd(*args, **kwargs)[source]

Bases: sporco.admm.cbpdn.ConvBPDNMaskDcpl

ADMM algorithm for a Convolutional Sparse Coding problem with an \(\ell_1\) data fidelity term and both \(\ell_1\) and \(\ell_2\) of gradient regularisation terms [52].


Inheritance diagram of ConvL1L1Grd


Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; \left\| W \left(\sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s}\right) \right\|_1 + \lambda \sum_m \| \mathbf{x}_m \|_1 + (\mu/2) \sum_i \sum_m \| G_i \mathbf{x}_m \|_2^2\;\;,\]

where \(W\) is a mask array and \(G_i\) is an operator computing the derivative along index \(i\), via the ADMM problem

\[\begin{split}\mathrm{argmin}_{\mathbf{x},\mathbf{y}_0,\mathbf{y}_1} \; \| W \mathbf{y}_0 \|_1 + \lambda \| \mathbf{y}_1 \|_1 + (\mu/2) \sum_i \| \Gamma_i \mathbf{x} \|_2^2 \;\text{such that}\; \left( \begin{array}{c} D \\ I \end{array} \right) \mathbf{x} - \left( \begin{array}{c} \mathbf{y}_0 \\ \mathbf{y}_1 \end{array} \right) = \left( \begin{array}{c} \mathbf{s} \\ \mathbf{0} \end{array} \right) \;\;,\end{split}\]

where \(D \mathbf{x} = \sum_m \mathbf{d}_m * \mathbf{x}_m\) and

\[\begin{split}\Gamma_i = \left( \begin{array}{ccc} G_i & 0 & \ldots \\ 0 & G_i & \ldots \\ \vdots & \vdots & \ddots \end{array} \right) \;\;.\end{split}\]

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) \| W (\sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s}) \|_1\)

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

RegGrad : Value of regularisation term \((1/2) \sum_i \sum_m \| G_i \mathbf{x}_m \|_2^2\)

PrimalRsdl : Norm of primal residual

DualRsdl : Norm of dual residual

EpsPrimal : Primal residual stopping tolerance \(\epsilon_{\mathrm{pri}}\)

EpsDual : Dual residual stopping tolerance \(\epsilon_{\mathrm{dua}}\)

Rho : Penalty parameter

XSlvRelRes : Relative residual of X step solver

Time : Cumulative run time


Call graph

../_images/cl1l1grd_init.svg

Parameters
Darray_like

Dictionary matrix

Sarray_like

Signal vector or matrix

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (gradient)

Warray_like

Mask array. The array shape must be such that the array is compatible for multiplication with input array S (see cnvrep.mskWshape for more details).

optConvL1L1Grd.Options object

Algorithm options

dimK0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimNint, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.ConvBPDNMaskDcpl.Options

ConvL1L1Grd algorithm options

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

GradWeight : An array of weights \(w_m\) for the term penalising the gradient of the coefficient maps. If this option is defined, the gradient regularization term is \(\sum_i \sum_m w_m \| G_i \mathbf{x}_m \|_2^2\) where \(w_m\) is the weight for filter index \(m\). The array should be an \(M\)-vector where \(M\) is the number of filters in the dictionary.

Parameters
optdict or None, optional (default None)

ConvL1L1Grd algorithm options

setdict(D=None)[source]

Set dictionary array.

xstep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{x}\).

ystep()[source]

Minimise Augmented Lagrangian with respect to \(\mathbf{y}\).

eval_objfn()[source]

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

obfn_g0(Y0)[source]

Compute \(g_0(\mathbf{y}_0)\) component of ADMM objective function.

rsdl_s(Yprev, Y)[source]

Compute dual residual vector.

rsdl_sn(U)[source]

Compute dual residual normalisation term.

rhochange()[source]

Updated cached c array when rho changes.

solve()

Call graph

../_images/cl1l1grd_solve.svg
class sporco.admm.cbpdn.MultiDictConvBPDN(cbpdnclass, D, S, *args, **kwargs)[source]

Bases: object

Solve a convolutional sparse coding problem fitting a single set of coefficient maps to multiple dictionaries and signals, e.g.

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \left\| D_0 \mathbf{x} - \mathbf{s}_0 \right\|_2^2 + (1/2) \left\| D_1 \mathbf{x} - \mathbf{s}_1 \right\|_2^2 + \lambda \| \mathbf{x} \|_1 \;\;,\]

for input images \(\mathbf{s}_0\), \(\mathbf{s}_1\), dictionaries \(D_0\) and \(D_0\), and coefficient map set \(\mathbf{x}\), where \(D_0 \mathbf{x} = \sum_m \mathbf{d}_{0,m} \mathbf{x}_m\) and \(D_1 \mathbf{x} = \sum_m \mathbf{d}_{1,m} \mathbf{x}_m\).

Implemented as a wrapper about a ConvBPDN or derived object (or any other object with sufficiently similar interface and internals).

Parameters
cbpdnclassclass name

Type of internal cbpdn object (e.g. cbpdn.ConvBPDN) to be constructed

Dtuple of array_like

Set of dictionary arrays

Stuple of array_like

Set of signal arrays

*args

Variable length list of arguments for constructor of internal cbpdn object

**kwargs

Keyword arguments for constructor of internal cbpdn object

solve()[source]

Call the solve method of the inner cbpdn object and return the result.

getcoef()[source]

Call the getcoef method if the inner cbpdn object.

getitstat()[source]

Get iteration stats from inner cbpdn object.

reconstruct(b, X=None)[source]

Reconstruct representation of signal b in signal set.