1
$\begingroup$

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
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Vedran Šego
    Commented Aug 22, 2013 at 14:02
  • $\begingroup$ @VedranŠego: You are right. I miss typed. Thanks $\endgroup$
    – Hernan
    Commented Aug 22, 2013 at 15:10

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. It works quite nice most of the times. Look at my edit. $\endgroup$
    – Hernan
    Commented Aug 24, 2013 at 12:08
  • $\begingroup$ @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. $\endgroup$
    – Noah Stein
    Commented Aug 26, 2013 at 13:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .