MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


0 2 2 1

I want to obtain:

0 0 0 1 2

and not

0 2 2 1 0
share|cite|improve this question
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
up vote 3 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.