Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
1  
What does closest mean? (It's not most close, by the way) –  Thierry Zell Oct 30 '10 at 13:09
3  
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
add comment

4 Answers 4

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Thank You very much ! –  Alexander Chervov Apr 17 '11 at 5:27
add comment

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

share|improve this answer
    
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
add comment

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!

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.