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?



Sparse approximate representation of a collection of vectors
By triangle inequality, preserving the property you wish for means that you can find "representatives" for each $v$ so that the $\ell\_1$ distances between any $v, v'$ are preserved to within 2$\epsilon$ additive error. 


There is a general result by Brinkman and Charikar that says that in general, for a collection of $n$ vectors in an $\ell\_1$ space, there's no way to construct a set of $n$ vectors in a smaller (e.g $\log n$) dimensional space) that preserves distances approximately even multiplicatively (let alone additively). This distinction is important if you have vectors in the original space that are $O(\epsilon)$ apart, but otherwise doesn't matter greatly. 


Brinkman, B. and Charikar, M. 2005. On the impossibility of dimension reduction in l1. J. ACM 52, 5 (Sep. 2005), 766-788. DOI= <http://doi.acm.org/10.1145/1089023.1089026> 


So I'm guessing that the answer to your first question should be no. 


