pylops.optimization.sparsity.OMP

pylops.optimization.sparsity.OMP(Op, data, niter_outer=10, niter_inner=40, sigma=0.0001, normalizecols=False, show=False)[source]

Orthogonal Matching Pursuit (OMP).

Solve an optimization problem with \(L0\) regularization function given the operator Op and data y. 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

data : numpy.ndarray

Data

niter_outer : int

Number of iterations of outer loop

niter_inner : int

Number of iterations of inner loop

sigma : list

Maximum L2 norm of residual. When smaller stop iterations.

normalizecols : list

Normalize columns (True) or not (False). Note that this can be expensive as it requires applying the forward operator \(n_{cols}\) times to unit vectors (i.e., containing 1 at position j and zero otherwise); use only when the columns of the operator are expected to have highly varying norms.

show : bool, optional

Display iterations log

Returns:
xinv : numpy.ndarray

Inverted model

iiter : int

Number of effective outer iterations

cost : numpy.ndarray, optional

History of cost function

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{d}\):

\[||\mathbf{x}||_0 \quad subj. to \quad ||\mathbf{Op}\mathbf{x}-\mathbf{b}||_2 <= \sigma,\]

using Orthogonal Matching Pursuit (OMP). This is a very simple iterative algorithm which applies the following step:

\[\begin{split}\Lambda_k = \Lambda_{k-1} \cup \{ arg max_j |\mathbf{Op}_j^H \mathbf{r}_k| \} \\ \mathbf{x}_k = \{ arg min_{\mathbf{x}} ||\mathbf{Op}_{\Lambda_k} \mathbf{x} - \mathbf{b}||_2\end{split}\]

Examples using pylops.optimization.sparsity.OMP