MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Does $\|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
That's the Hamming metric which is also the same as the $L^1$ norm and counts the number of coordinates where they differ. So they differ at $\epsilon$ positions. I'm wondering what values of $\epsilon$ the OP has in mind though. The problem is interesting, but quite broad as it is. – Sonia Balagopalan Jan 29 '10 at 19:14
Is there a particular reason why you want the size of $span(b_1,\ldots,b_k)$ to be roughly the same as the size of $C$, which is the dimension of the space. Just curious! – Sonia Balagopalan Jan 29 '10 at 19:25
I'm interested in the $\ell_1$ norm, not necessarily the $\ell_\infty$ norm (Hamming). I am willing to let $b_i \in \mathbb{R}^n$, so they are not necessarily the same. $||u-v||_1 = \sum_{i=1}^n|u_i-v_i|$. I'm thinking of values of $\epsilon = c\dot n$ for some constant $c < 1$, the smaller the better. Sonia -- I'm thinking of approximating the value of an exponentially sized set of functions over a domain given a polynomially sized set of evaluations (of possibly different functions) over the same domain. – Donald Jan 29 '10 at 19:58
up vote 4 down vote accepted

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=

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

share|cite|improve this answer
The Brinkman-Charikar examples are the diamond graphs, which live in the Hamming cube. The only positive result for $\ell_1$ is that $n$ vectors well embed into $\ell_1^k$ with $k$ of order $n\log$n! Probably you know that you can do what you want if you are in $\ell_2$; if not, Google "Johnson-Lindenstrauss Lemma". – Bill Johnson Jan 30 '10 at 18:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.