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 [48] 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]

Base class for ADMM algorithm for solving variants of the Basis Pursuit DeNoising (BPDN) [11] 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: 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(self, D)[source]

Set dictionary array.

getcoef(self)[source]

Get final coefficient array.

xstep(self)[source]

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

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

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

obfn_dfd(self)[source]

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

obfn_reg(self)[source]

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

itstat_extra(self)[source]

Non-standard entries for the iteration stats record tuple.

rhochange(self)[source]

Re-factorise matrix when rho changes.

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

ADMM algorithm for the Basis Pursuit DeNoising (BPDN) [11] 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$

$\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: 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(self, ushape)[source]

Return initialiser for working variable U

ystep(self)[source]

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

obfn_reg(self)[source]

Compute regularisation term and contribution to objective function.

solve(*args)

Call graph

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

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

$\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: 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(self)[source]

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

obfn_reg(self)[source]

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

solve(*args)

Call graph

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

ADMM algorithm for the elastic net [48] 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$

$\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: 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(self, D)[source]

Set dictionary array.

xstep(self)[source]

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

obfn_reg(self)[source]

Compute regularisation term and contribution to objective function.

rhochange(self)[source]

Re-factorise matrix when rho changes.

solve(*args)

Call graph

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

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 [32], 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$

$\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: D : array_like, shape (N, M) Dictionary matrix S : array_like, shape (N, K) Signal vector or matrix gamma : float Constraint parameter opt : 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(self, ushape)[source]

Return initialiser for working variable U.

ystep(self)[source]

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

eval_objfn(self)[source]

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

solve(*args)

Call graph

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

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$

$\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: 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 : 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(self, ushape)[source]

Return initialiser for working variable U.

setdict(self, D)[source]

Set dictionary array.

getcoef(self)[source]

Get final coefficient array.

xstep(self)[source]

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

ystep(self)[source]

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

cnst_A1(self, X)[source]

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

cnst_A1T(self, X)[source]

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

eval_objfn(self)[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(self, Yprev, Y)[source]

Compute dual residual vector.

rsdl_sn(self, U)[source]

Compute dual residual normalisation term.

solve(*args)

Call graph