Finding the smallest subset of a set of vectors which contains another vector in the span Consider a set $S=\{ \underline{v_1},\dots , \underline{v_n}  \} $ of vectors of dimension $d<n$. Suppose for some vector $\underline{b}$ that the solution space for the matrix equation
$\left[ \underline{v_1}  \dots \underline{v_n} \right] \underline{x} = \underline{b} $
is nonempty. I wish to find the smallest subset $S'=\{\underline{v_1'},  \dots, \underline{v_m'} \} \subseteq S$ such that the solution space of the equation
$ \left[\underline{v_1'}  \dots \underline{v_m'} \right] \underline{x'} = \underline{b}$
is still nonempty.
Clearly $S'$ should be a linearly independent set, but that does not narrow down the choices much. Is there a way to solve this cleverly without examining the span of each possible subset of $S$?
Thoughts on a solution:
One could compute the space of solutions of the first equation, and then attempt to construct one solution with as many $0$ entries as possible, but I am not sure how one would go about doing this either.
Ultimately, I hope to employ this to find interesting relations between elements of a vector space by decomposing some special element "efficiently" over a basis.
 A: What you're looking for here is a "sparse solution" to a system of equations.
In other words, we're looking for the solution to the problem 
$$
\left[\begin{array}{cccc}
v_1 & v_2 & \cdots & v_n
\end{array} \right]\vec x= A \vec x=\vec b
$$
So that the column vector $\vec x$ has the lowest possible number of entries.  Another way to put this is that we're trying to minimize $\|\vec x\|_0$ (the number of non-zero entries, also called the "support" or "zero-norm" of $\vec x$) under the constraint that $A \vec x=\vec b$.  This is a difficult and practical problem, which is the subject of current research.  For more information on all that, I'd recommend looking into "compressed sensing" and "sparse recovery".
To give you a little bit of a heads up: solving this efficiently requires using some property of $A$ to your advantage.  One such family of matrices is the family of matrices $A$ that satisfy the "restricted isometry property".  If $A$ has a sufficiently small "RIP constant" (lower than $\frac13$) then the problem can be solved by minimizing $\|\vec x\|_1$ under the same constraints, which is a problem that can be solved by linear programming.
