# 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

## 1 Answer

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. See this wikipedia page or try googling things like "sparsest vector", "LASSO", "Orthogonal Matching Pursuit".

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.

-
Thanks. It works quite nice most of the times. Look at my edit. –  Hernan Aug 24 '13 at 12:08
@Hernan: You're welcome. Unfortunately I don't know much about the details of this algorithm. The recommended procedure on MO for asking follow-up questions is to post a new question which links to the old one; you would probably get more answers this way since some people are more likely to look at questions which do not yet have an accepted answer. –  Noah Stein Aug 26 '13 at 13:41
Thanks. I will do that. –  Hernan Aug 26 '13 at 19:15