Parallel ADMM algorithm for Convolutional BPDN

Classes

 ParConvBPDN(D, S[, lmbda, W, opt, nproc, …]) Parallel ADMM algorithm for Convolutional BPDN (CBPDN) with or without a spatial mask [29].

## Class Descriptions¶

class sporco.admm.parcbpdn.ParConvBPDN(D, S, lmbda=None, W=None, opt=None, nproc=None, ngrp=None, dimK=None, dimN=2)[source]

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

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: 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 nproc : int Number of processes ngrp : int Number of groups in partition of filter indices 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

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: opt : dict or None, optional (default None) ParConvBPDN algorithm options
solve()[source]

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()[source]

Initialize multiprocessing pool if necessary.

distribute(f, n)[source]

Distribute the computations amongst the multiprocessing pools

Parameters: f : function Function to be distributed to the processors n : int The values in range(0,n) will be passed as arguments to the function f.
terminate_pool()[source]

Terminate and close the multiprocessing pool if necessary.

obfn_gvar()[source]

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

obfn_fvar()[source]

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

obfn_reg()[source]

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

obfn_dfd()[source]

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