# Finding the most compact representation of a vector in an “overdetermined base”

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

-
Shouldn't it be 0 0 0 1 2? How do you define "the most compact"? Only in terms of the number of (non)zero elements, or is there something else as well? – Vedran Šego Aug 22 '13 at 14:02
@VedranŠego: You are right. I miss typed. Thanks – Hernan Aug 22 '13 at 15:10

None of these methods will guarantee the sparsest solution with a particular fixed choice of vectors $B$. But if the set $B$ is large then maybe you don't care about having the exact smallest representation as long as you get a decent one. If the set $B$ is small (as in the example you gave), of course you can enumerate all the subsets and try them one by one.