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: 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: 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

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

Default content and allowed dict keys

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

Fields in IterationStats associated with the objective function; see eval_objfn

itstat_fields_extra = ('XSlvRelRes',)

Non-standard fields in IterationStats; see itstat_extra

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

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'DFid': 'DFid', 'Fnc': 'ObjFun', 'Reg': 'Reg'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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: 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: 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

defaults = {'AbsStopTol': 0.0, 'AutoRho': {'AutoScaling': True, 'Enabled': True, 'Period': 10, 'RsdlRatio': 1.2, 'RsdlTarget': None, 'Scaling': 1000.0, 'StdResiduals': False}, 'AuxVarObj': True, 'Callback': None, 'DataType': None, 'FastSolve': False, 'IterTimer': 'solve', 'L1Weight': 1.0, 'LinSolveCheck': False, 'MaxMainIter': 1000, 'NonNegCoef': False, 'RelStopTol': 0.001, 'RelaxParam': 1.8, 'ReturnX': False, 'StatusHeader': True, 'U0': None, 'Verbose': False, 'Y0': None, 'fEvalX': False, 'gEvalY': True, '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', 'Regℓ1')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'DFid': 'DFid', 'Fnc': 'ObjFun', 'Regℓ1': 'RegL1'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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: 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

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

Fields in IterationStats associated with the objective function; see eval_objfn

hdrtxt_objfn = ('Fnc', 'DFid', 'Regℓ1', 'Regℓ2,1')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'DFid': 'DFid', 'Fnc': 'ObjFun', 'Regℓ1': 'RegL1', 'Regℓ2,1': 'RegL21'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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: 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

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

Fields in IterationStats associated with the objective function; see eval_objfn

hdrtxt_objfn = ('Fnc', 'DFid', 'Regℓ1', 'Regℓ2')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'DFid': 'DFid', 'Fnc': 'ObjFun', 'Regℓ1': 'RegL1', 'Regℓ2': 'RegL2'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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: 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: Options

BPDNProjL1 algorithm options

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

Parameters:

optdict or None, optional (default None)

BPDNProjL1 algorithm options

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

Default content and allowed dict keys

itstat_fields_objfn = ('ObjFun', 'Cnstr')

Fields in IterationStats associated with the objective function; see eval_objfn

hdrtxt_objfn = ('Fnc', 'Cnstr')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'Cnstr': 'Cnstr', 'Fnc': 'ObjFun'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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: 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: 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

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

Default content and allowed dict keys

itstat_fields_objfn = ('ObjFun', 'Cnstr')

Fields in IterationStats associated with the objective function; see eval_objfn

hdrtxt_objfn = ('Fnc', 'Cnstr')

Display column headers associated with the objective function; see eval_objfn

hdrval_objfun = {'Cnstr': 'Cnstr', 'Fnc': 'ObjFun'}

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

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