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]

Base class for ADMM algorithm for solving variants of the Convolutional BPDN (CBPDN) [28] [32] [30] problem.

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 : 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]

ADMM algorithm for the Convolutional BPDN (CBPDN) [28] [32] [30] problem.

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

Parameters: D : array_like Dictionary array S : array_like Signal array lmbda : float Regularisation parameter opt : 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

class sporco.admm.cbpdn.ConvBPDNJoint(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

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).

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

Parameters: D : array_like Dictionary array S : array_like Signal array lmbda : float Regularisation parameter (l1) mu : float Regularisation parameter (l2,1) opt : 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

class sporco.admm.cbpdn.ConvElasticNet(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

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

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$

$\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

Parameters: D : array_like Dictionary matrix S : array_like Signal vector or matrix lmbda : float Regularisation parameter (l1) mu : float Regularisation parameter (l2) opt : 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

class sporco.admm.cbpdn.ConvBPDNGradReg(D, S, lmbda=None, mu=0.0, opt=None, dimK=None, dimN=2)[source]

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

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

Parameters: D : array_like Dictionary matrix S : array_like Signal vector or matrix lmbda : float Regularisation parameter (l1) mu : float Regularisation parameter (gradient) opt : 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

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

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

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

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$

$\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

Parameters: D : array_like Dictionary matrix S : array_like Signal vector or matrix gamma : float Constraint parameter opt : 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

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

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$$.

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 : 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]

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

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$

$\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

Parameters: D : array_like Dictionary matrix S : array_like Signal vector or matrix epsilon : float $$\ell_2$$ ball radius opt : 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

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

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

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

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

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.