# how to find vector $(\pm 1, \pm 1, \pm 1, … \pm 1)$ which is most close to given vector (r_1,…r_l) ? Is it NP-problem ? What algorithms are available ?

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

-
What does closest mean? (It's not most close, by the way) – Thierry Zell Oct 30 '10 at 13:09
This a different kind of question than where the NP issue applies. You're asking for some method of preprocessing information about the $V_i$ that makes decoding quick per real number instance of $R_j$. In fact the method of brute force testing is already polynomial in the size of the input $\{ V_i\} \cup \{R_j\}$. – Bill Thurston Oct 30 '10 at 13:55
We cannot tell whether you want the $V_i$ which is nearest in terms of Euclidean distance or in terms of the angle between the vectors, or perhaps some third manner of measuring closeness. If it is Euclidean distance the length of the vector $R$ itself heavily influences this, a rough trichotomy given by $| R | < , = , > \sqrt l$ – Will Jagy Oct 30 '10 at 21:09
1) On R^n we consider standard Eucleadian distance. (But if you have an idea for any other distance is is also heartly welcome). So closest in this sense, i.e. vector v_i such that distance ||R- v_i|| is smallest one. 2) I want to consider polynomiality in the log(size(V_i)). (e.g. l=20 , n=2^10). – Alexander Chervov Oct 31 '10 at 6:18

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.

-

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.

-
Thank You very much ! – Alexander Chervov Apr 17 '11 at 5:27

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").

-
Wow ! Very interesting argument ! I need to think. Just some remark: R \in {+-1}^l - is measure zero for me, solutions for some special choices of Vi which I know, uses that R is in general position - something like step 1: choose max(|ri|) take its sign sgn(ri), ... Most probably it will not affect yours arguments, however.... – Alexander Chervov Nov 3 '10 at 4:38

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!

-
Thank You ! But from what I can see in en.wikipedia.org/wiki/Semidefinite_programming this theme is about max-min on the space of positive matrices. But in this problem Vi - vectors, not matrices. How to deal with it ? – Alexander Chervov Nov 3 '10 at 4:12