Escasa representación aproximada de una colección de vectores

Question

Supongamos que tengo una colección de $n$ vectores $C \subset \mathbb{F}_2^n$. Ellos son, por supuesto, que comprende el conjunto canónico de $n$ vectores de la base.

Lo que me gustaría encontrar es mucho más pequeño (~ $\log n$) colección de vectores de la base que abarcan una colección de vectores que bien aproximados $C$. Que es, me gustaría base de vectores $b_1,\ldots,b_k$ tal que para cada a $v \in C$, existe un $u \in span(b_1,\ldots,b_k)$ tal que $||u-v||_1 \leq \epsilon$.

Cuando esto es posible? Hay una propiedad que $C$ podría poseer a permitir esa escasa aproximación?

Answer 1

Por el triángulo de la desigualdad, la preservación de la propiedad que usted desea significa que usted puede encontrar a los "representantes" para cada una de las $v$, de modo que el $\ell_1$ distancias entre cualquier $v, v'$ se conservan dentro de 2$\epsilon$ de aditivo de error.

No es un resultado general por Brinkman y Charikar que dice que, en general, para una colección de $n$ vectores en un $\ell_1$ espacio, no hay manera de construir una serie de $n$ vectores en un pequeño (e.g $\log n$) de espacio tridimensional) que preserva distancias de aproximadamente incluso multiplicatively (y no digamos de forma aditiva). Esta distinción es importante si usted tiene vectores en el espacio original que se $O(\epsilon)$ aparte, pero por lo demás no importa mucho.

Brinkman, B. y Charikar, M. 2005. En la imposibilidad de reducción de dimensiones en la l1. J. ACM 52, 5 (Sep. 2005), 766-788. DOI= http://doi.acm.org/10.1145/1089023.1089026

Así que supongo que la respuesta a la primera pregunta debería ser no.