sparse.greedy_pursuit.orthogonal_matching_pursuit

sparse.greedy_pursuit.orthogonal_matching_pursuit(mat_a, b, n_nonzero_coefs, least_squares=False, tol=1e-06)

Orthogonal Matching Pursuit (OMP) algorithm finds an approximate solution to (1) s.t. \(\|x\|_0 \le k\) in exactly k (n_nonzero_coefs) steps. Orthogonality means that the same atom is chosen from a dictionary of columns of mat_a no more than once.

Parameters

mat_a(N, M) np.ndarray

The input weight matrix \(\boldsymbol{A}\).

b(N,) np.ndarray

The right side of the equation (1).

n_nonzero_coefsint

\(k\), the maximum number of non-zero coefficients in \(\vec{x}\).

least_squaresbool, optional

If set to True, uses Least Squares OMP (LS-OMP) method instead of OMP (False). Default is False (OMP).

tolfloat, optional

The tolerance which determines when a solution is “close enough” to the optimal solution. Compared with L2-norm of residuals (errors) at each iteration.

Returns

Solution

Refer to Greedy Matching Pursuit algorithms.

Notes

If the true unknown \(\vec{x}_{\text{true}}\) to be found is sparse enough,

(1)\[\|\vec{x}_{\text{true}}\|_0 = s < \frac{1}{2} \left( 1 + \frac{1}{\mu\{ \boldsymbol{A} \}} \right)\]

where \(\mu\{ \boldsymbol{A} \}\) is the mutual coherence of the input matrix mat_a (see sparse.coherence.mutual_coherence()), then WMP, MP, OMP, and LS-OMP are guaranteed to find it.