Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:59:36Z http://mathoverflow.net/feeds/question/100342 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/100342/are-there-subsets-l-in-rn-such-that-it-is-easy-to-find-closest-point-in-l-to-a Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes Alexander Chervov 2012-06-22T10:19:42Z 2012-06-25T13:27:41Z <p>Math Motivation: consider LINEAR subspace $L$ in $R^n$ and given vector $E$ in $R^n$, then it is easy to find a closest vector $S \in L$ to $E$ - just ortogonal projection. </p> <p><strong>Question</strong> Are they some interesting examples/constructions of non-linear manifolds/subsets $L$ in $R^n$ such that solve similar question for it is also "easy" ?</p> <p>Well, "easy" means - not just direct use of some minimization algorithm...</p> <hr> <p>Telecom motivation: set $L$ is set of signals which we want to "transmit", the map $L \to R^n$ is "error correcting coding" (i.e. adding redundant information), after the "transmission" due to noise we get point $E$ which might be out of the original set $L$. The "decoding" is the search of point $S$ in $L$ which is most close to received with errors point $E$. </p> <p>So in the language of telecom theory my question is: <strong>how to build code which is "easy" to "decode"</strong>. (At the moment I forget about the other important requirment - that code should correct as many errors as better)</p> <hr> <p>There is clearly huge literature in coding theory. But may be some fresh look "ab initio" would be helpful (at least to clarify my mind).</p> http://mathoverflow.net/questions/100342/are-there-subsets-l-in-rn-such-that-it-is-easy-to-find-closest-point-in-l-to-a/100345#100345 Answer by NN for Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes NN 2012-06-22T11:06:59Z 2012-06-22T12:12:21Z <p>From your requirements I cannot understand whether this qualifies: point that realizes the distance between a closed convex set and a given point (distance for a complete uniformly convex norm). Perhaps you should be more specific in your question.</p> <p>Edit: I do not understand the meaning of "easy" for you. But I also know pratically nothing about coding theory. If you clarify "easy" for your context, perhaps someone else can give you more useful answers.</p> http://mathoverflow.net/questions/100342/are-there-subsets-l-in-rn-such-that-it-is-easy-to-find-closest-point-in-l-to-a/100355#100355 Answer by Pietro Majer for Are there subsets L in R^n such that it is "easy to find" closest point in L to a given P in R^n ? Vague question motivated by error-correcting codes Pietro Majer 2012-06-22T13:37:46Z 2012-06-22T13:56:36Z <p>Actually I only have a vague idea of how "easy" the minimization problem should be, and how "large" the class of sets $L.$ Clearly, the optimal balance between these aspects depends on the scopes you have in mind.</p> <p>The simplest sets $L$, after linear subspaces and of course spheres, are possibly the ellipsoids; although the theory for the corresponding point-set distance problem is clear, a complete solution seems not so cheap to me.</p> <p>Let $A$ be a positive definite symmetric matrix of order $n$, and let $L$ be the ellipsoid $\{x\in\mathbb{R}^n\ : \ (Ax\cdot x)\le 1 \}$. Let $p\in\mathbb{R}^n$ not in $L$, that is satisfying $(Ap\cdot p) > 1$. The unique minimizer $x\in L$ of the (squared) distance from $p$, $|x-p|^2$ satisfies $$p-x=\lambda Ax$$ for some Lagrange multiplier $\lambda\ge0$, which is determined by the condition $x\in\partial L$, that is $(Ax\cdot x)= 1$. Since $\lambda\ge0$, the operator $(I+\lambda A)$ is invertible, and we have then $x=(I+\lambda A)^{-1}p$, so $Ax=(I+\lambda A)^{-1}Ap$, and $$1=(Ax\cdot x)=\big( (I+\lambda A)^{-2} Ap\cdot p\big )$$ If $A$ has eigenvalues $0\le\alpha_1\le\dots\le\alpha _ n$ and if the coordinates of $p$ in the spectral basis are $p_1,\dots, p _ n$. the latter equation for $\lambda$ may be written $$1=\sum_{k=1}^n \frac{\alpha_k p_k^2}{(1+\lambda \alpha_ k)^2}$$ The RHS is indeed a strictly decreasing function of $\lambda$, vanishing at infinity, with value $(Ap\cdot p) > 1$ at $\lambda=0$, showing that it has exactly one positive solution $\lambda$, as it has to be. However, I do not know a quick solution of this equation, for all values of $(p_1,\dots p_n)$. Maybe a sub-class of ellipsoids (that is, special values of $\alpha_1,\dots \alpha_n$) do allow nice solutions.</p>