Suppose I have a collection of $n$ vectors $C \subset \mathbb{F}_2^n$. They are of course spanned by the canonical set of $n$ basis vectors.

What I would like to find is a much smaller (~ $\log n$) collection of basis vectors that span a collection of vectors which well approximate $C$. That is, I would like basis vectors $b_1,\ldots,b_k$ such that for every $v \in C$, there exists a $u \in span(b_1,\ldots,b_k)$ such that $||u-v||_1 \leq \epsilon$.

When is this possible? Is there a property that $C$ might posses to allow such a sparse approximation?

`$\|u-v\|<\varepsilon$`

mean that $u$ and $v$ differ in at most $\varepsilon n$ positions or you normalize the norm in some other way? – fedja Jan 29 '10 at 18:33