I want 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.

For example

    1 0 0 0
    0 1 0 0
    0 0 1 0
    0 0 0 1
    0 1 1 0

Given 

    0 2 2 1

I want to obtain:
    
    0 0 0 1 2

and not

    0 2 2 1 0

Edit: problem using this idea
----

I have tried to use [scikit-learn OrthogonalMatchingPursuit][1] 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?


  [1]: http://scikit-learn.org/stable/auto_examples/linear_model/plot_omp.html