sporco.admm.bpdn

Classes for ADMM algorithm for the BPDN problem

Classes

GenericBPDN(D, S[, opt]) Base class for ADMM algorithm for solving variants of the Basis Pursuit DeNoising (BPDN) [11] problem.
BPDN(D, S[, lmbda, opt]) ADMM algorithm for the Basis Pursuit DeNoising (BPDN) [11] problem.
BPDNJoint(D, S[, lmbda, mu, opt]) ADMM algorithm for BPDN with joint sparsity via an \(\ell_{2,1}\) norm term.
ElasticNet(D, S[, lmbda, mu, opt]) ADMM algorithm for the elastic net [42] problem.
BPDNProjL1(D, S, gamma[, opt]) ADMM algorithm for a BPDN variant with projection onto the \(\ell_1\) ball instead of an \(\ell_1\) penalty.
MinL1InL2Ball(D, S, epsilon[, opt]) ADMM algorithm for the problem with an \(\ell_1\) objective and an \(\ell_2\) constraint.

Class Descriptions

class sporco.admm.bpdn.GenericBPDN(D, S, opt=None)[source]

Bases: sporco.admm.admm.ADMMEqual

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


Inheritance diagram of GenericBPDN


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:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (N, K)

Signal vector or matrix

opt : BPDN.Options object

Algorithm options

class Options(opt=None)[source]

Bases: sporco.admm.admm.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:
opt : dict or None, optional (default None)

GenericBPDN algorithm options

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

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

Re-factorise matrix when rho changes.

class sporco.admm.bpdn.BPDN(D, S, lmbda=None, opt=None)[source]

Bases: sporco.admm.bpdn.GenericBPDN

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


Inheritance diagram of BPDN


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

../_images/bpdn_init.svg

Parameters:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (N, K)

Signal vector or matrix

lmbda : float

Regularisation parameter

opt : BPDN.Options object

Algorithm options

class Options(opt=None)[source]

Bases: sporco.admm.bpdn.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:
opt : dict or None, optional (default None)

BPDN 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/bpdn_solve.svg
class sporco.admm.bpdn.BPDNJoint(D, S, lmbda=None, mu=0.0, opt=None)[source]

Bases: sporco.admm.bpdn.BPDN

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


Inheritance diagram of BPDNJoint


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

../_images/bpdnjnt_init.svg

Parameters:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (M, K)

Signal vector or matrix

lmbda : float

Regularisation parameter (l1)

mu : float

Regularisation parameter (l2,1)

opt : BPDN.Options object

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/bpdnjnt_solve.svg
class sporco.admm.bpdn.ElasticNet(D, S, lmbda=None, mu=0.0, opt=None)[source]

Bases: sporco.admm.bpdn.BPDN

ADMM algorithm for the elastic net [42] problem.


Inheritance diagram of ElasticNet


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

../_images/elnet_init.svg

Parameters:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (M, K)

Signal vector or matrix

lmbda : float

Regularisation parameter (l1)

mu : float

Regularisation parameter (l2)

opt : BPDN.Options object

Algorithm options

setdict(D)[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.

rhochange()[source]

Re-factorise matrix when rho changes.

solve()

Call graph

../_images/elnet_solve.svg
class sporco.admm.bpdn.BPDNProjL1(D, S, gamma, opt=None)[source]

Bases: sporco.admm.bpdn.GenericBPDN

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


Inheritance diagram of BPDNProjL1


This variant of the BPDN problem was originally referred to as the lasso [27], 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

../_images/bpdnprjl1_init.svg

Parameters:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (N, K)

Signal vector or matrix

gamma : float

Constraint parameter

opt : BPDNProjL1.Options object

Algorithm options

class Options(opt=None)[source]

Bases: sporco.admm.bpdn.Options

BPDNProjL1 algorithm options

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

Parameters:
opt : dict or None, optional (default None)

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

solve()

Call graph

../_images/bpdnprjl1_solve.svg
class sporco.admm.bpdn.MinL1InL2Ball(D, S, epsilon, opt=None)[source]

Bases: sporco.admm.admm.ADMMTwoBlockCnstrnt

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


Inheritance diagram of MinL1InL2Ball


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

../_images/bpdnml1l2_init.svg

Parameters:
D : array_like, shape (N, M)

Dictionary matrix

S : array_like, shape (N, K)

Signal vector or matrix

epsilon : float

\(\ell_2\) ball radius

opt : MinL1InL2Ball.Options object

Algorithm options

class Options(opt=None)[source]

Bases: sporco.admm.admm.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:
opt : dict or None, optional (default None)

MinL1InL2Ball algorithm options

uinit(ushape)[source]

Return initialiser for working variable U.

setdict(D)[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}\).

cnst_A1(X)[source]

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

cnst_A1T(X)[source]

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

eval_objfn()[source]

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

Compute dual residual vector.

rsdl_sn(U)[source]

Compute dual residual normalisation term.

solve()

Call graph

../_images/bpdnml1l2_solve.svg