pylops.optimization.cls_sparsity.OMP¶
- class pylops.optimization.cls_sparsity.OMP(Op, callbacks=None)[source]¶
Orthogonal Matching Pursuit (OMP).
Solve an optimization problem with \(L_0\) regularization function given the operator
Op
and datay
. The operator can be real or complex, and should ideally be either square \(N=M\) or underdetermined \(N<M\).- Parameters
- Op
pylops.LinearOperator
Operator to invert
- Op
See also
ISTA
Iterative Shrinkage-Thresholding Algorithm (ISTA).
FISTA
Fast Iterative Shrinkage-Thresholding Algorithm (FISTA).
SPGL1
Spectral Projected-Gradient for L1 norm (SPGL1).
SplitBregman
Split Bregman for mixed L2-L1 norms.
Notes
Solves the following optimization problem for the operator \(\mathbf{Op}\) and the data \(\mathbf{y}\):
\[\|\mathbf{x}\|_0 \quad \text{subject to} \quad \|\mathbf{Op}\,\mathbf{x}-\mathbf{y}\|_2^2 \leq \sigma^2,\]using Orthogonal Matching Pursuit (OMP). This is a very simple iterative algorithm which applies the following step:
\[\begin{split}\DeclareMathOperator*{\argmin}{arg\,min} \DeclareMathOperator*{\argmax}{arg\,max} \Lambda_k = \Lambda_{k-1} \cup \left\{\argmax_j \left|\mathbf{Op}_j^H\,\mathbf{r}_k\right| \right\} \\ \mathbf{x}_k = \argmin_{\mathbf{x}} \left\|\mathbf{Op}_{\Lambda_k}\,\mathbf{x} - \mathbf{y}\right\|_2^2\end{split}\]Note that by choosing
niter_inner=0
the basic Matching Pursuit (MP) algorithm is implemented instead. In other words, instead of solving an optimization at each iteration to find the best \(\mathbf{x}\) for the currently selected basis functions, the vector \(\mathbf{x}\) is just updated at the new basis function by taking directly the value from the inner product \(\mathbf{Op}_j^H\,\mathbf{r}_k\).In this case it is highly recommended to provide a normalized basis function. If different basis have different norms, the solver is likely to diverge. Similar observations apply to OMP, even though mild unbalancing between the basis is generally properly handled.
Methods
__init__
(Op[, callbacks])callback
(x, *args, **kwargs)Callback routine
finalize
(x, cols[, show])Finalize solver
run
(x, cols[, show, itershow])Run solver
setup
(y[, niter_outer, niter_inner, sigma, ...])Setup solver
solve
(y[, niter_outer, niter_inner, sigma, ...])Run entire solver
step
(x, cols[, show])Run one step of solver