sporco.admm.parcbpdn

Parallel ADMM algorithm for Convolutional BPDN

Classes

ParConvBPDN(*args, **kwargs)

Parallel ADMM algorithm for Convolutional BPDN (CBPDN) with or without a spatial mask [42].

Class Descriptions

class sporco.admm.parcbpdn.ParConvBPDN(*args, **kwargs)

Bases: GenericConvBPDN

Parallel ADMM algorithm for Convolutional BPDN (CBPDN) with or without a spatial mask [42].

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 \left( \sum_l \mathbf{y}_{0,l} - \mathbf{s} \right) \|_2^2 + \lambda \| \mathbf{y}_1 \|_1 \;\text{such that}\; \left( \begin{array}{c} D_{G_0} \\ \vdots \\ D_{G_{L-1}} \\ \alpha I \end{array} \right) \mathbf{x} - \left( \begin{array}{c} \mathbf{y}_{0,0} \\ \vdots \\ \mathbf{y}_{0,L-1} \\ \alpha \mathbf{y}_1 \end{array} \right) = \left( \begin{array}{c} \mathbf{0} \\ \vdots \\ \mathbf{0} \\ \mathbf{0} \end{array} \right) \;\;,\end{split}\]

where the \(M\) dictionary filters are partitioned into \(L\) groups, \(\{G_l\}_{l \in \{0,\dots,L-1\}}\) where

\[G_i \cap G_j = \emptyset \text{ for } i \neq j \text{ and } \bigcup_l G_l = \{0, \dots, M-1\} \;,\]

and \(D_{G_l}\) is a linear operator such that \(D_{G_l} \mathbf{x} = \sum_{g \in G_l} \mathbf{d}_g * \mathbf{x}_g\).

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

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

with input images \(\mathbf{s}_k\), masks \(W_k\), and coefficient maps \(\mathbf{x}_{k,m}\). The multi-channel problem with input image channels \(\mathbf{s}_c\) and a multi-channel mask \(W_c\) is either

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \sum_c \left\| W_c \left( \sum_m \mathbf{d}_m * \mathbf{x}_{c,m} - \mathbf{s}_c \right) \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\| W_c \left( \sum_m \mathbf{d}_{c,m} * \mathbf{x}_m - \mathbf{s}_c \right) \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, AttributeError 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 \left( \sum_m \mathbf{d}_m * \mathbf{x}_m - \mathbf{s} \right) \|_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 : Not Implemented (relative residual of X step solver)

Time : Cumulative run time

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 input array S (see cnvrep.mskWshape for more details).

optParConvBPDN.Options object

Algorithm options

nprocint

Number of processes

ngrpint

Number of groups in partition of filter indices

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)

Bases: Options

ParConvBPDN algorithm options

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

alpha : A float indicating the relative weight between the constraint \(D_{G_l} \mathbf{x} = \mathbf{y}_{0,l}\) and \(\alpha \mathbf{x} = \mathbf{y}_1\). None value effectively defaults to no weight or \(\alpha = 1\).

Y0 : Initial value for \(\mathbf{y}_0\).

U0 : Initial value for \(\mathbf{u}_0\).

Y1 : Initial value for \(\mathbf{y}_1\).

U1 : Initial value for \(\mathbf{u}_1\).

and the exceptions:

AutoRho : Not implemented.

LinSolveCheck : Not implemented.

Parameters:

optdict or None, optional (default None)

ParConvBPDN algorithm options

defaults = {'AbsStopTol': 0.0, 'AutoRho': {'AutoScaling': True, 'Enabled': True, 'Period': 1, 'RsdlRatio': 1.2, 'RsdlTarget': None, 'Scaling': 1000.0, 'StdResiduals': False}, 'AuxVarObj': False, 'Callback': None, 'DataType': None, 'FastSolve': False, 'HighMemSolve': False, 'IterTimer': 'solve', 'L1Weight': 1.0, 'LinSolveCheck': False, 'MaxMainIter': 1000, 'NoBndryCross': False, 'NonNegCoef': False, 'RelStopTol': 0.001, 'RelaxParam': 1.8, 'ReturnX': False, 'StatusHeader': True, 'U0': None, 'U1': None, 'Verbose': False, 'Y0': None, 'Y1': None, 'alpha': None, 'fEvalX': True, 'gEvalY': False, 'rho': None}

Default content and allowed dict keys

itstat_fields_objfn = ('ObjFun', 'DFid', 'RegL1')

Fields in IterationStats associated with the objective function; see eval_objfn

hdrtxt_objfn = ('Fnc', 'DFid', 'Regl1')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'DFid': 'DFid', 'Fnc': 'ObjFun', 'Regl1': 'RegL1'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

solve()

Start (or re-start) optimisation. This method implements the framework for the iterations of an ADMM algorithm.

If option Verbose is True, the progress of the optimisation is displayed at every iteration. At termination of this method, attribute itstat is a list of tuples representing statistics of each iteration, unless option FastSolve is True and option Verbose is False.

Attribute timer is an instance of util.Timer that provides the following labelled timers:

init: Time taken for object initialisation by __init__

solve: Total time taken by call(s) to solve

solve_wo_func: Total time taken by call(s) to solve, excluding time taken to compute functional value and related iteration statistics

solve_wo_rsdl : Total time taken by call(s) to solve, excluding time taken to compute functional value and related iteration statistics as well as time take to compute residuals and implemented AutoRho mechanism

init_pool()

Initialize multiprocessing pool if necessary.

distribute(f, n)

Distribute the computations amongst the multiprocessing pools

Parameters:

ffunction

Function to be distributed to the processors

nint

The values in range(0,n) will be passed as arguments to the function f.

terminate_pool()

Terminate and close the multiprocessing pool if necessary.

obfn_gvar()

Variable to be evaluated in computing ADMM.obfn_g, depending on the gEvalY option value.

obfn_fvar()

Variable to be evaluated in computing ADMM.obfn_f, depending on the fEvalX option value.

obfn_reg()

Compute regularisation term, \(\| x \|_1\), and contribution to objective function.

obfn_dfd()

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