sparse.greedy_pursuit.thresholding_algorithm

sparse.greedy_pursuit.thresholding_algorithm(mat_a, b, n_nonzero_coefs)

Thresholding algorithm is the fastest and least accurate among greedy pursuit algorithms of finding an approximate solution to (1).

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}\).

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{\mid x_{min} \mid}{\mid x_{max} \mid} \cdot \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 the Thresholding algorithm is guaranteed to find it.