sporco.admm.cbpdn

Classes for ADMM algorithm for the Convolutional BPDN problem

Classes

GenericConvBPDN(D, S[, opt, dimK, dimN]) Base class for ADMM algorithm for solving variants of the Convolutional BPDN (CBPDN) [28] [32] [30] problem.
ConvBPDN(D, S[, lmbda, opt, dimK, dimN]) ADMM algorithm for the Convolutional BPDN (CBPDN) [28] [32] [30] problem.
ConvBPDNJoint(D, S[, lmbda, mu, opt, dimK, dimN]) ADMM algorithm for Convolutional BPDN with joint sparsity via an \(\ell_{2,1}\) norm term [30] (the \(\ell_2\) norms are computed over the channel index).
ConvElasticNet(D, S[, lmbda, mu, opt, dimK, …]) ADMM algorithm for a convolutional form of the elastic net problem [42].
ConvBPDNGradReg(D, S[, lmbda, mu, opt, …]) ADMM algorithm for an extension of Convolutional BPDN including a term penalising the gradient of the coefficient maps [31].
ConvBPDNProjL1(D, S, gamma[, opt, dimK, dimN]) ADMM algorithm for a ConvBPDN variant with projection onto the \(\ell_1\) ball instead of an \(\ell_1\) penalty.
ConvTwoBlockCnstrnt(D, S[, opt, dimK, dimN]) Base class for ADMM algorithms for problems of the form
ConvMinL1InL2Ball(D, S, epsilon[, opt, …]) ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint, following the general approach proposed in [2].
ConvBPDNMaskDcpl(D, S, lmbda[, W, opt, …]) ADMM algorithm for Convolutional BPDN with Mask Decoupling [19].
AddMaskSim(cbpdnclass, D, S, W, *args, **kwargs) Boundary masking for convolutional representations using the Additive Mask Simulation (AMS) technique described in [29].

Class Descriptions

class sporco.admm.cbpdn.GenericConvBPDN(D, S, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.admm.ADMMEqual

Base class for ADMM algorithm for solving variants of the Convolutional BPDN (CBPDN) [28] [32] [30] 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:
D : array_like

Dictionary array

S : array_like

Signal array

opt : GenericConvBPDN.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial/temporal dimensions

class Options(opt=None)[source]

Bases: sporco.admm.admm.Options

ConvBPDN 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:
opt : dict 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(D, S, lmbda=None, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.cbpdn.GenericConvBPDN

ADMM algorithm for the Convolutional BPDN (CBPDN) [28] [32] [30] 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:
D : array_like

Dictionary array

S : array_like

Signal array

lmbda : float

Regularisation parameter

opt : ConvBPDN.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial/temporal dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.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:
opt : dict 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(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

ADMM algorithm for Convolutional BPDN with joint sparsity via an \(\ell_{2,1}\) norm term [30] (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:
D : array_like

Dictionary array

S : array_like

Signal array

lmbda : float

Regularisation parameter (l1)

mu : float

Regularisation parameter (l2,1)

opt : ConvBPDNJoint.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.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:
opt : dict 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(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

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


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:
D : array_like

Dictionary matrix

S : array_like

Signal vector or matrix

lmbda : float

Regularisation parameter (l1)

mu : float

Regularisation parameter (l2)

opt : ConvBPDN.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, 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(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.cbpdn.ConvBPDN

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


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:
D : array_like

Dictionary matrix

S : array_like

Signal vector or matrix

lmbda : float

Regularisation parameter (l1)

mu : float

Regularisation parameter (gradient)

opt : ConvBPDNGradReg.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.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:
opt : dict 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(D, S, gamma, opt=None, dimK=None, dimN=2)[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 [28] for single-channel dictionaries, and the solver from [30] 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:
D : array_like

Dictionary matrix

S : array_like

Signal vector or matrix

gamma : float

Constraint parameter

opt : ConvBPDNProjL1.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.Options

ConvBPDNProjL1 algorithm options

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

Parameters:
opt : dict 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(D, S, opt=None, dimK=None, dimN=2)[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:
D : array_like

Dictionary array

S : array_like

Signal array

opt : ConvTwoBlockCnstrnt.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.admm.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:
opt : dict 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(D, S, epsilon, opt=None, dimK=None, dimN=2)[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 [28] for single-channel dictionaries, and the solver from [30] 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:
D : array_like

Dictionary matrix

S : array_like

Signal vector or matrix

epsilon : float

\(\ell_2\) ball radius

opt : ConvMinL1InL2Ball.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.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:
opt : dict 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(D, S, lmbda, W=None, opt=None, dimK=None, dimN=2)[source]

Bases: sporco.admm.cbpdn.ConvTwoBlockCnstrnt

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


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:
D : array_like

Dictionary matrix

S : array_like

Signal vector or matrix

lmbda : float

Regularisation parameter

W : array_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).

opt : ConvBPDNMaskDcpl.Options object

Algorithm options

dimK : 0, 1, or None, optional (default None)

Number of dimensions in input signal corresponding to multiple independent signals

dimN : int, optional (default 2)

Number of spatial dimensions

class Options(opt=None)[source]

Bases: sporco.admm.cbpdn.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:
opt : dict 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 [29]. 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:
cbpdnclass : class name

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

D : array_like

Dictionary array

S : array_like

Signal array

W : array_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.