sporco.pgm.bpdn

Classes for PGM algorithm for the BPDN problem

Classes

BPDN(*args, **kwargs)	Class for PGM algorithm for the Basis Pursuit DeNoising (BPDN) [16] problem.
WeightedBPDN(*args, **kwargs)	Class for PGM algorithm for variant of BPDN with a weighted \(\ell_2\) data fidelity term.

Class Descriptions

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

Bases: PGM

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

The problem form is

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

where \(\mathbf{s}\) is the input vector/matrix, \(D\) is the dictionary, and \(\mathbf{x}\) is the sparse representation.

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 \(\lambda \| \mathbf{x} \|_1\)

Rsdl : Residual

L : Inverse of gradient step parameter

Time : Cumulative run time

Parameters:

Darray_like

Dictionary array (2d)

Sarray_like

Signal array (1d or 2d)

lmbdafloat

Regularisation parameter

optBPDN.Options object

Algorithm options

class Options(opt=None)

Bases: Options

BPDN algorithm options

Options include all of those defined in pgm.PGM.Options, together with additional options:

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

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 = {'AutoStop': {'Enabled': False, 'Tau0': 0.01}, 'Backtrack': None, 'Callback': None, 'DataType': None, 'FastSolve': False, 'IterTimer': 'solve', 'L': 500.0, 'L1Weight': 1.0, 'MaxMainIter': 1000, 'Momentum': <sporco.pgm.momentum.MomentumNesterov object>, 'Monotone': False, 'NonNegCoef': False, 'RelStopTol': 0.001, 'StatusHeader': True, 'StepSizePolicy': None, 'Verbose': False, 'X0': None}

Default content and allowed dict keys

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

Fields in IterationStats associated with the objective function; see eval_objfun

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

Display column headers associated with the objective function; see eval_objfun

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

Dictionary mapping display column headers in hdrtxt_objfn to IterationStats entries

setdict(D)

Set dictionary array.

getcoef()

Get final coefficient array.

grad_f(V=None)

Compute gradient of data fidelity for variable V or self.Y.

prox_g(V)

Compute proximal operator of \(g\).

hessian_f(V)

Compute Hessian of \(f\) applied to V.

eval_objfn()

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

obfn_reg()

Compute regularisation term and contribution to objective function.

obfn_f(X=None)

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

reconstruct(X=None)

Reconstruct representation.

class sporco.pgm.bpdn.WeightedBPDN(*args, **kwargs)

Bases: BPDN

Class for PGM algorithm for variant of BPDN with a weighted \(\ell_2\) data fidelity term.

The problem form is

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

where \(\mathbf{s}\) is the input vector/matrix, \(D\) is the dictionary, \(\mathbf{x}\) is the sparse representation, and \(\| \cdot \|_W\) denotes the weighted \(\ell_2\) norm defined as

\[\| \mathbf{x} \|_W = \| W^{1/2} \mathbf{x} \|_2 \;.\]

While this norm is defined for any symmetric positive definite \(W\), the interface of this class only supports diagonal \(W\) in that the W parameter of the constructor is actually a vector \(\mathbf{w}\) such that \(W = \mathrm{diag}(\mathbf{w})\).

When the input is a matrix, i.e. the problem is of the form

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

where \(S\) and \(X\) are matrices rather than vectors, it is important to note that \(\| \cdot \|_W\) does not denote the standard weighted Frobenius norm \(\| X \|_W = \| W^{1/2} X W^{1/2} \|_F\), and is instead defined as

\[\| X \|_W^2 = \| W^{1/2} \odot X \|_F\]

so that

\[\| X \|_W^2 = \sum_i \| W_i^{1/2} \mathbf{x}_i \|_2^2 = \sum_i \| \mathbf{x}_i \|_{W_i}^2 \;,\]

where \(\mathbf{x}_i\) and \(\mathbf{w}_i\) are the \(i^{\text{th}}\) columns of \(X\) and \(W\) respectively, and \(W_i = \mathrm{diag}(\mathbf{w}_i)\).

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} \|_W^2\)

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

Rsdl : Residual

L : Inverse of gradient step parameter

Time : Cumulative run time

Parameters:

Darray_like

Dictionary array (2d)

Sarray_like

Signal array (1d or 2d)

lmbdafloat

Regularisation parameter

Warray_like

Weight array (1d or 2d)

optWeightedBPDN.Options object

Algorithm options

grad_f(V=None)

Compute gradient of data fidelity for variable V or self.Y.

obfn_f(X=None)

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