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

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

2012-06-22T10:19:42Z

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.

Question 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" ?

Well, "easy" means - not just direct use of some minimization algorithm...

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$.

So in the language of telecom theory my question is: how to build code which is "easy" to "decode". (At the moment I forget about the other important requirment - that code should correct as many errors as better)

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

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

2012-06-22T11:06:59Z

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.

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.

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

2012-06-22T13:37:46Z

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.

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.

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.