What's wrong with my implementation of the Matching Pursuit algorithm?

I have recently attempted to implement a simple version of the Matching Pursuit algorithm, following the description detailed on Wikipedia. Although the algorithm itself seems dead simple, my implementation produces very suboptimal results in some cases (i.e. the inner product between the represented signal and the sparse reconstruction is very small).

Here is the Python function I have written, x is the input signal and D is the dictionary matrix with normalized rows.

import numpy as np
import numpy.linalg as la

def matching_pursuit(x: np.ndarray,
D: np.ndarray,
eps_min: np.float64 = 1e-3,
iter_max: int = 1000) -> np.ndarray:

s = np.zeros(D.shape, dtype=np.float64)

r = x.astype(np.float64)
for _ in range(iter_max):
dot = np.dot(D, r)
i = np.argmax(np.abs(dot))

s[i] = dot[i]
r -= s[i] * D[i, :]

if la.norm(r) < eps_min:
break

return s

As an example, for a randomly generated matrix D equal to:

[[0.09365858 0.65561007 0.74926865]
[0.24806947 0.62017367 0.74420841]
[0.08804509 0.70436073 0.70436073]
[0.54545455 0.54545455 0.63636364]
[0.62469505 0.46852129 0.62469505]
[0.68100522 0.59587957 0.42562827]
[0.64465837 0.72524067 0.24174689]
[0.24077171 0.48154341 0.84270097]
[0.58834841 0.19611614 0.78446454]
[0.80178373 0.26726124 0.53452248]
[0.45584231 0.56980288 0.68376346]
[0.36214298 0.81482171 0.45267873]
[0.19802951 0.69310328 0.69310328]
[0.74535599 0.59628479 0.2981424 ]
[0.76249285 0.45749571 0.45749571]
[0.19802951 0.69310328 0.69310328]
[0.46829291 0.74926865 0.46829291]
[0.70014004 0.14002801 0.70014004]
[0.76626103 0.28734789 0.57469577]
[0.93704257 0.31234752 0.15617376]]

and an input signal x = [1, 2, 3] the function returns

[ 0.          0.          0.          0.          0.          0.
0.00119178 -0.00095663 -0.00167583  0.          0.          0.
0.          0.          0.          0.          0.          0.
0.          0.        ]

which results, when multiplied with the dictionary matrix again, in x = [-4.48011162e-04, 7.50118419e-05, -1.83267255e-03].

Now what I'm wondering is whether I have made some mistake in my implementation or whether this is an expected outcome due to the nature of the algorithm and/or properties of these specific sample inputs.

• Where did your data come from? did you just randomize it? Dec 26 '18 at 13:00
• Yes, I just used np.random.randint to create D. Dec 26 '18 at 13:01
• It is difficult to folllow your program without having the main part. However, the approximation of $x$ is equal to $\sum_i s_i D_i$. It does not seem to be provided by the program Dec 26 '18 at 14:15

In general, the picking of the dictionary $$D$$ is a very important point in the MP algorithm. I recommend you take a look in the following link as well as researching a bit more yourself. The Fourier matrix, for example, is a common choice for the dictionary.