6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – fedja
    Jan 29, 2010 at 18:33
  • $\begingroup$ 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. $\endgroup$ Jan 29, 2010 at 19:14
  • $\begingroup$ 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! $\endgroup$ Jan 29, 2010 at 19:25
  • $\begingroup$ 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. $\endgroup$
    – Donald
    Jan 29, 2010 at 19:58

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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". $\endgroup$ Jan 30, 2010 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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