Given a real vector $R = (r_1, \dots, r_l)$ and a set of $n$ distinct vectors

$$\begin{array}{c} V_1 = (c_{1,1}, \dots, c_{1,l})\\ V_2 = (c_{2,1}, \dots, c_{2,l})\\ \vdots\\\ V_n=(c_{n,1}, \dots, c_{n,l}) \end{array}$$

where $c_{i,j} \in \{\pm 1\}$ and $n \lt 2^l$. Note that if $n = 2^l$ then the problem is trivial.

**Problem:** How to find the vector $V_i$ whose Euclidean distance to $R$ is minimal? (Suggestions on any other distances are also welcome).

Of course, using brute force we can check all $V_i$, but is there any way to reduce the search space? The set of vectors $V_k$ is fixed once and forever, while vector $R$ is coming every millisecond, and the algorithm should quickly "decode" $R$ to some $V_i$.

**Sub-problems:**

Is this problem NP-hard? I.e., is it possible to have an algorithm polynomial in $\log(n)$? It is true for some special cases like the trivial case $n=2^l$, but what about more generally?

Given some "hint" vector $V_k$, is it possible to answer a question "is it the right answer or not" in some computationally simple way?

Given some "hint" vector $V_k$, is it possible to improve it in some way?

**P.S.**

Does the distance function have only global minima? Or does it also have local minima on the set $V_i$? More precisely, one should speak about "$\epsilon$-local minima" for some $\epsilon$. I.e., the set of vectors $V_i$ is a metric space (induce metric from $\mathbb R^n$). Let us say some function $f$ has an "$\epsilon$-local minimum" at some point $V_k$ of this set if $f(V_k) < f(V_i)$ for all $V_i \in \epsilon$ - neighborhood $V_k$).

Consider a distance function from the given vector $R = (r_1, \dots, r_l)$ to $V_i$. What is the smallest $\epsilon$ for which any $\epsilon$-local minimum is a global minimum? How does it depends on input vector $R=(r_1, \dots, r_l)$?

closestmean? (It's not most close, by the way) $\endgroup$ – Thierry Zell Oct 30 '10 at 13:09