Given: some vector $R=(r_1...r_l)$ - real numbers, and a set of distinct vectors with $+1$ or $-1$ coordinates $$\begin{array}{c} V_1=(c_{1,1} ... c_{1,l}),\\\ V_2=(c_{2,1} ... c_{2,l}),\\\ .....\\\ V_n=(c_{n,1} ... c_{n,l})\end{array}$$ each $c_{i,j}$ are $+1$ or $-1$. $n\lt 2^l$ is some number (if $n=2^l$ - problem is trivial.)

** Problem:**
How to find vector $V_i$ which is the most close to $R$ ? ( in the sense of Euclidean distance (suggestions on any other distances are also welcome)).

Of course, we by brute force can check all $V_i$, but is there any way to reduce brute force ? Set of vectors $V_k$ is fixed once and forever, $R$ is coming every millisecond, and algorithm should quickly "decode" $R$ to some $V_i$.

Sub-problems: Is this problem NP-hard ? ( i.e. Is it possible to have algorithm polynomial in the log(n) ? (It is true for some special cases like trivial n=2^l. But what about more general ?))

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

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

PS

Does distance function have only global or also local minimums on the set $V_i$ ?

More precisely one should speak about "$\epsilon$-local minimums" for some $\epsilon$.

I.e.

Set of vectors $V_i$ is a metric space (induce metric from $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 given vector $R=(r_1...r_l)$ to $V_i$.

What is the smallest $\epsilon$ for which any $\epsilon$-local minimum is global minimum ?

How it depends on input vector $R=(r_1...r_l)$ ?

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