## Sparse approximate representation of a collection of vectors

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

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 2010 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 2010 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 2010 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 2010 at 19:58

## 1 Answer

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.

-

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 2010 at 18:31
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 39, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9230031371116638, "perplexity_flag": "head"}