4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ What does closest mean? (It's not most close, by the way) $\endgroup$
    – Thierry Zell
    Commented Oct 30, 2010 at 13:09
  • 3
    $\begingroup$ 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\}$. $\endgroup$
    – Bill Thurston
    Commented Oct 30, 2010 at 13:55
  • $\begingroup$ 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$ $\endgroup$
    – Will Jagy
    Commented Oct 30, 2010 at 21:09
  • $\begingroup$ 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). $\endgroup$
    – Alexander Chervov
    Commented Oct 31, 2010 at 6:18

4 Answers 4

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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.... $\endgroup$
    – Alexander Chervov
    Commented Nov 3, 2010 at 4:38
0
$\begingroup$

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!

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .