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.

Methods

__init__(Op[, callbacks])
callback(x, *args, **kwargs)	Callback routine
finalize([show])	Finalize solver
run(x[, 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[, show, show_inner])	Run one step of solver