sporco.admm.bpdn

Classes for ADMM algorithm for the BPDN problem

Classes

GenericBPDN(*args, **kwargs)	Base class for ADMM algorithm for solving variants of the Basis Pursuit DeNoising (BPDN) [16] problem.
BPDN(*args, **kwargs)	ADMM algorithm for the Basis Pursuit DeNoising (BPDN) [16] problem.
BPDNJoint(*args, **kwargs)	ADMM algorithm for BPDN with joint sparsity via an \(\ell_{2,1}\) norm term.
ElasticNet(*args, **kwargs)	ADMM algorithm for the elastic net [64] problem.
BPDNProjL1(*args, **kwargs)	ADMM algorithm for a BPDN variant with projection onto the \(\ell_1\) ball instead of an \(\ell_1\) penalty.
MinL1InL2Ball(*args, **kwargs)	ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint.

Class Descriptions

class sporco.admm.bpdn.GenericBPDN(*args, **kwargs)

Bases: sporco.admm.admm.ADMMEqual

Base class for ADMM algorithm for solving variants of the Basis Pursuit DeNoising (BPDN) [16] problem.

The generic problem form is

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2 + g(\mathbf{x}) \;\;,\]

where \(g(\cdot)\) is a penalty term or the indicator function of a constraint, and is solved via the ADMM problem

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

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

Time : Cumulative run time

Parameters

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (N, K)

Signal vector or matrix

optBPDN.Options object

Algorithm options

class Options(opt=None)

Bases: sporco.admm.admm.ADMMEqual.Options

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

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

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

Parameters

optdict or None, optional (default None)

GenericBPDN algorithm options

setdict(D)

Set dictionary array.

getcoef()

Get final coefficient array.

xstep()

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

ystep()

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. When it is overridden, it should be explicitly called at the end of the overriding method.

eval_objfn()

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

obfn_dfd()

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

obfn_reg()

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

itstat_extra()

Non-standard entries for the iteration stats record tuple.

rhochange()

Re-factorise matrix when rho changes.

class sporco.admm.bpdn.BPDN(*args, **kwargs)

Bases: sporco.admm.bpdn.GenericBPDN

ADMM algorithm for the Basis Pursuit DeNoising (BPDN) [16] problem.

Solve the Single Measurement Vector (SMV) BPDN problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2 + \lambda \| \mathbf{x} \|_1\]

via the ADMM problem

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

The Multiple Measurement Vector (MMV) BPDN problem

\[\mathrm{argmin}_X \; (1/2) \| D X - S \|_F^2 + \lambda \| X \|_1\]

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

DFid : Value of data fidelity term \((1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2\)

RegL1 : Value of regularisation term \(\| \mathbf{x} \|_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

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (N, K)

Signal vector or matrix

lmbdafloat

Regularisation parameter

optBPDN.Options object

Algorithm options

class Options(opt=None)

Bases: sporco.admm.bpdn.GenericBPDN.Options

BPDN algorithm options

Options include all of those defined in GenericBPDN.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. If this option is defined, the regularization term is \(\lambda \| \mathbf{w} \odot \mathbf{x} \|_1\) where \(\mathbf{w}\) denotes the weighting array.

Parameters

optdict or None, optional (default None)

BPDN algorithm options

uinit(ushape)

Return initialiser for working variable U

ystep()

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

obfn_reg()

Compute regularisation term and contribution to objective function.

solve()

Call graph

class sporco.admm.bpdn.BPDNJoint(*args, **kwargs)

Bases: sporco.admm.bpdn.BPDN

ADMM algorithm for BPDN with joint sparsity via an \(\ell_{2,1}\) norm term.

Solve the optimisation problem

\[\mathrm{argmin}_X \; (1/2) \| D X - S \|_2^2 + \lambda \| X \|_1 + \mu \| X \|_{2,1}\]

via the ADMM problem

\[\mathrm{argmin}_{X, Y} \; (1/2) \| D X - S \|_2^2 + \lambda \| Y \|_1 + \mu \| Y \|_{2,1} \quad \text{such that} \quad X = Y \;\;.\]

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) \| D X - S \|_2^2\)

RegL1 : Value of regularisation term \(\| X \|_1\)

RegL21 : Value of regularisation term \(\| X \|_{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

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (M, K)

Signal vector or matrix

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (l2,1)

optBPDN.Options object

Algorithm options

ystep()

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

obfn_reg()

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

solve()

Call graph

class sporco.admm.bpdn.ElasticNet(*args, **kwargs)

Bases: sporco.admm.bpdn.BPDN

ADMM algorithm for the elastic net [64] problem.

Solve the optimisation problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2 + \lambda \| \mathbf{x} \|_1 + (\mu/2) \| \mathbf{x} \|_2^2\]

via the ADMM problem

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

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) \| D \mathbf{x} - \mathbf{s} \|_2^2\)

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

RegL2 : Value of regularisation term \((1/2) \| \mathbf{x} \|_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

Time : Cumulative run time

Call graph

Parameters

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (M, K)

Signal vector or matrix

lmbdafloat

Regularisation parameter (l1)

mufloat

Regularisation parameter (l2)

optBPDN.Options object

Algorithm options

setdict(D)

Set dictionary array.

xstep()

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

obfn_reg()

Compute regularisation term and contribution to objective function.

rhochange()

Re-factorise matrix when rho changes.

solve()

Call graph

class sporco.admm.bpdn.BPDNProjL1(*args, **kwargs)

Bases: sporco.admm.bpdn.GenericBPDN

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

This variant of the BPDN problem was originally referred to as the lasso [46], but that name is now also frequently applied to the penalised form that is referred to here as the BPDN problem.

Solve the problem

\[\mathrm{argmin}_\mathbf{x} \; (1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2 \; \text{such that} \; \| \mathbf{x} \|_1 \leq \gamma\]

via the ADMM problem

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

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 BPDN problem (see BPDN), 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.

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 \((1/2) \| D \mathbf{x} - \mathbf{s} \|_2^2\)

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

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (N, K)

Signal vector or matrix

gammafloat

Constraint parameter

optBPDNProjL1.Options object

Algorithm options

class Options(opt=None)

Bases: sporco.admm.bpdn.GenericBPDN.Options

BPDNProjL1 algorithm options

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

Parameters

optdict or None, optional (default None)

BPDNProjL1 algorithm options

uinit(ushape)

Return initialiser for working variable U.

ystep()

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

eval_objfn()

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

solve()

Call graph

class sporco.admm.bpdn.MinL1InL2Ball(*args, **kwargs)

Bases: sporco.admm.admm.ADMMTwoBlockCnstrnt

ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint.

The solution is computed following the approach proposed in [2].

Solve the Single Measurement Vector (SMV) problem

\[\mathrm{argmin}_\mathbf{x} \| \mathbf{x} \|_1 \; \text{such that} \; \| D \mathbf{x} - \mathbf{s} \|_2 \leq \epsilon\]

via the ADMM problem

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

where \(\iota_{C(\mathbf{s}, \epsilon)}(\cdot)\) is the indicator function of the \(\ell_2\) ball of radius \(\epsilon\) about \(\mathbf{s}\). The Multiple Measurement Vector (MMV) problem

\[\mathrm{argmin}_X \| X \|_1 \; \text{such that} \; \| [D X - S]_k \|_2 \leq \epsilon \;\;\; \forall k \;\;,\]

where \([X]_k\) denotes column \(k\) of matrix \(X\), 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

Darray_like, shape (N, M)

Dictionary matrix

Sarray_like, shape (N, K)

Signal vector or matrix

epsilonfloat

\(\ell_2\) ball radius

optMinL1InL2Ball.Options object

Algorithm options

class Options(opt=None)

Bases: sporco.admm.admm.ADMMTwoBlockCnstrnt.Options

MinL1InL2Ball algorithm options

Options include all of those defined in admm.ADMMTwoBlockCnstrnt.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. 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)

MinL1InL2Ball algorithm options

uinit(ushape)

Return initialiser for working variable U.

setdict(D)

Set dictionary array.

getcoef()

Get final coefficient array.

xstep()

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

ystep()

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

cnst_A1(X)

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

cnst_A1T(X)

Compute \(A_1^T \mathbf{x}\) where \(A_1 \mathbf{x}\) is a component of ADMM problem constraint.

eval_objfn()

Compute components of objective function as well as total contribution to objective function. The objective function is \(\| \mathbf{x} \|_1\) and the constraint violation measure is \(P(\mathbf{x}) - \mathbf{x}\) where \(P(\mathbf{x})\) is the projection into the constraint set.

rsdl_s(Yprev, Y)

Compute dual residual vector.

rsdl_sn(U)

Compute dual residual normalisation term.

solve()

Call graph