Question

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)$ ?

Answer 1

Let the $R_i$ be $\pm 1$ vectors and the $V_i$ be a linear space over GF(2). This then becomes the problem of maximum likelihood decoding of binary linear codes, which is known to be an NP-hard problem. It thus seems likely (although it doesn't follow rigorously) that there's no good way of doing this better than brute force.

Answer 2

If you restrict to the case where $R \in \{ \pm1 \}^l$ you can encode an arbitrary function $f\colon \{\pm1\}^l\to \pm1$ with appropriate choice of the $V_i$ by augmenting your problem to instead return $1$ if $R = V_i$ for some $i$ and $-1$ otherwise. If you have an algorithm to solve your original problem then you can solve the augmented problem without adding much by first finding the closest $V_i$ and then checking if $V_i=R$. Since the augmented problem can encode any function it will in general have exponential circuit complexity, and therefore the original problem will also have exponential circuit complexity (and therefore has no subexponential "algorithm").

Answer 3

This problem is NP-hard. It is known (as it has been already mentioned) as the decoding of linear block codes. Here is the reference of the intractability result

E.R. BERLEKAMP, R.J. MCELIECE, and H.C.A. VAN TILBORG, "On the inherent intractability of certain coding problems," IEEE Trans. Inform. Theory, vol. 24, pp. 384– 386, May 1978.

There are some nice relaxations, such as the LP decoder that was introduced in

J. Feldman, M.J. Wainwright and D.R. Karger, "Using linear programming to Decode Binary linear codes," IEEE Transactions on Information Theory, 51:954–972, March 2005.

Answer 4

You may use the concept of semidefinite relaxation (way of arriving at the class of convex semidefinite programs) to solve this problem. This will involve the trick of using the cyclic property of trace operator. Cheers!