Minimum number vectors "spanning another vector" Let $S = \{v_1,\dots,v_n\}$ be a set of vectors in an $m$-dimnesional linear vector space $V$ with $n>m$. Given an arbitrary $x \in V$, how can we determine the minimal subset $S' \subset S$ such that $x \in \operatorname{span}(S')$?  
 A: This is a good question, and an important one to ask in the field of compressed sensing.  Here's a way we can reframe the question: 
For a vector $y \in \Bbb R^n$, let $\|y\|_0$ denote the number of entries that $y$ has which are non-zero.  So, for example, $\|(1, 0, 0, -3.5, 7, .01)\|_0 = 4$ (this metric is referred to as the "zero-norm" colloquially).  Let $A$ be the matrix whose columns are $v_1,\dots,v_n$ in that order.  The problem which we want to solve is

Minimize $\|y\|_0$ subject to the constraint $Ay = x$

Which is to say that we want the "sparsest" solution $y$ to our linear system.
A nice general approach is this: it can be shown that, if $n$ is much larger than $m$, then solving

Minimize $\|y\|_1$ subject to the constraint $Ay = x$

gives you a solution which is necessarily "close" to the best possible answer (here, $\|y\|_1 = \sum_{i=1}^m |y_i|$).  The above problem can be solved using linear programming techniques.
A: The most efficient way I see is:


*

*Look at all linearly independent subsets $S_i\subset S$ that span $S$ (i.e., all linearly independent subsets of size $m$ of $S$). There should be fewer than ${n\choose m}$ of them.

*For every $i$, find the (unique) scalars $\alpha_1^i,\dots, \alpha_m^i$ such that $$\sum_{k=1}^m\alpha_k^i v_i=x$$

*Pick $j$ as that value of $i$ for which $S_i$ for which the largest number of $\alpha_k^i$ is equal to $0$.

*Your final set is $S^*= \{v_k| \alpha_k^j\neq 0\}$

