Greedy Matching Pursuit algorithms

Greedy Pursuit algorithms solve an approximate problem

(1)\[\min_x{ \|\vec{b} - \boldsymbol{A} \vec{x} \|_2^2} \quad \text{s.t.} \ \|x\|_0 \le k\]

of \(\text{P}_0\) problem of a system of linear equations

(2)\[\min_x{ \| x \|_0} \quad \text{s.t.} \ \boldsymbol{A} \vec{x} = \vec{b}\]

where \(k\) is the maximum number of non-zero real-valued coefficients (atoms) of \(\vec{x}\).

Each algorithm returns a Solution which is a namedtuple with the following attributes:

.x - \(\vec{x}_{\text{sparsest}}\) solution to (1)

.support - a list of atoms (non-zero elements of \(\vec{x}\))

.residuals - a list of residual vectors after each iteration

orthogonal_matching_pursuit(mat_a, b, ...[, ...])	Orthogonal Matching Pursuit (OMP) algorithm finds an approximate solution to (1) s.t.
matching_pursuit(mat_a, b, n_iters[, ...])	(Weak) Matching Pursuit (MP, WMP) algorithms find an approximate solution to (1).
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).