# Robust Orthogonal Match Pursuit

In a previous question I asked how to find the most compact representation of a vector as a linear combination of a set of vectors B. B has more elements (on purpose) that is needs to have to describe the subspace. After one of the answersI have tried to use scikit-learn OrthogonalMatchingPursuit to try to understand how it works. I was surprised that it works really well in certain cases, but not in others. At the end, I created this simple example. With this matrix (using a tolerance of 1e-15):

[[ 1.  0.  0.  0.]
[ 0.  1.  0.  0.]
[ 0.  0.  1.  0.]
[ 0.  0.  0.  1.]
[ 0.  1.  1.  0.]]


The following vector

[ 0.  2.  2.  1.]


results in:

[ 0.  0.  0.  1.  2.]


which is ok as Matrix * result =

[ 0.  2.  2.  1.]


However, if the vector is:

[ 0.  2.  1.  1.]


the algorithm yields:

[-1.  1.  0.  0.  0.]


which is not the right result as Matrix * result =

[-1.  1.  0.  0.]


Why is this? How can I avoid it?

-
This sounds more like a question about the internal workings of a particular piece of software, than a question about mathematics, and perhaps better addressed as a bug report to the people offering the software. –  Gerry Myerson Aug 26 at 23:13
@GerryMyerson: I was under the impression that this is not an implementation problem but rather an issue of the theoretical algorithm. In the answer to my previous question it was said: "This problem and various related problems are known to be NP-hard to solve exactly, but there has been a lot of work on efficient approximations." I was wondering if there is a convergence problem that could be checked for before starting to search. –  Hernan Aug 27 at 13:17