pylops.optimization.cls_sparsity.SplitBregman

class pylops.optimization.cls_sparsity.SplitBregman(Op, callbacks=None)

Split Bregman for mixed L2-L1 norms.

Solve an unconstrained system of equations with mixed \(L_2\) and \(L_1\) regularization terms given the operator Op, a list of \(L_1\) regularization terms RegsL1, and an optional list of \(L_2\) regularization terms RegsL2.

Parameters

Oppylops.LinearOperator

Operator to invert

Notes

Solve the following system of unconstrained, regularized equations given the operator \(\mathbf{Op}\) and a set of mixed norm (\(L^2\) and \(L_1\)) regularization terms \(\mathbf{R}_{2,i}\) and \(\mathbf{R}_{1,i}\), respectively:

\[J = \frac{\mu}{2} \|\textbf{y} - \textbf{Op}\,\textbf{x} \|_2^2 + \frac{1}{2}\sum_i \epsilon_{\mathbf{R}_{2,i}} \|\mathbf{y}_{\mathbf{R}_{2,i}} - \mathbf{R}_{2,i} \textbf{x} \|_2^2 + \sum_i \epsilon_{\mathbf{R}_{1,i}} \| \mathbf{R}_{1,i} \textbf{x} \|_1\]

where \(\mu\) is the reconstruction damping, \(\epsilon_{\mathbf{R}_{2,i}}\) are the damping factors used to weight the different \(L^2\) regularization terms of the cost function and \(\epsilon_{\mathbf{R}_{1,i}}\) are the damping factors used to weight the different \(L_1\) regularization terms of the cost function.

The generalized Split-Bergman algorithm [1] is used to solve such cost function: the algorithm is composed of a sequence of unconstrained inverse problems and Bregman updates.

The original system of equations is initially converted into a constrained problem:

\[J = \frac{\mu}{2} \|\textbf{y} - \textbf{Op}\,\textbf{x}\|_2^2 + \frac{1}{2}\sum_i \epsilon_{\mathbf{R}_{2,i}} \|\mathbf{y}_{\mathbf{R}_{2,i}} - \mathbf{R}_{2,i} \textbf{x}\|_2^2 + \sum_i \| \textbf{y}_i \|_1 \quad \text{subject to} \quad \textbf{y}_i = \mathbf{R}_{1,i} \textbf{x} \quad \forall i\]

and solved as follows:

\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \begin{align} (\textbf{x}^{k+1}, \textbf{y}_i^{k+1}) = \argmin_{\mathbf{x}, \mathbf{y}_i} \|\textbf{y} - \textbf{Op}\,\textbf{x}\|_2^2 &+ \frac{1}{2}\sum_i \epsilon_{\mathbf{R}_{2,i}} \|\mathbf{y}_{\mathbf{R}_{2,i}} - \mathbf{R}_{2,i} \textbf{x}\|_2^2 \\ &+ \frac{1}{2}\sum_i \epsilon_{\mathbf{R}_{1,i}} \|\textbf{y}_i - \mathbf{R}_{1,i} \textbf{x} - \textbf{b}_i^k\|_2^2 \\ &+ \sum_i \| \textbf{y}_i \|_1 \end{align}\end{split}\]

\[\textbf{b}_i^{k+1}=\textbf{b}_i^k + (\mathbf{R}_{1,i} \textbf{x}^{k+1} - \textbf{y}^{k+1})\]

The scipy.sparse.linalg.lsqr solver and a fast shrinkage algorithm are used within a inner loop to solve the first step. The entire procedure is repeated niter_outer times until convergence.

1

Goldstein T. and Osher S., “The Split Bregman Method for L1-Regularized Problems”, SIAM J. on Scientific Computing, vol. 2(2), pp. 323-343. 2008.

Attributes

ncpmodule

Array module used by the solver (obtained via pylops.utils.backend.get_array_module) ). Available only after setup is called.

isjaxbool

Whether the input data is a JAX array or not.

nregsL1int

Number of L1 regularization terms.

bnumpy.ndarray

Bregman update vector.

dnumpy.ndarray

Shrinked vector.

nregsL1int

Number of L2 regularization terms.

Regslist

List of L1 and L2 regularization terms.

epsRslist

List of L1 and L2 regularization dampings.

costnumpy.ndarray, optional

History of total cost function through iterations.

iiterint

Current iteration number. Available only after setup is called and updated at each call to step.

Methods

__init__(Op[, callbacks])
callback(x, *args, **kwargs)	Callback routine
finalize([show])	Finalize solver
memory_usage([nopRegsL1, nopRegsL2, show, unit])	Compute memory usage of the solver
run(x[, engine, show, itershow, show_inner])	Run solver
setup(y, RegsL1[, x0, niter_outer, ...])	Setup solver
solve(y, RegsL1[, x0, niter_outer, ...])	Run entire solver
step(x[, engine, show, show_inner])	Run one step of solver