# 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

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

-
Can you give examples of the subsets which are of interest in your application? – Stanislav Jun 22 '12 at 11:03
@Stanislav real life codes - means you should have a discrete subset in R^n, such that the distance between points is big, but diameter is small... But it is complicated, I rather vaguely asking about "nice mathematical constructions" which are might be "close" to this question, e.g. may be for some Grassmanianns naturally embedded in P^n will satisfy the property that we can project on it in "easy way" or something mathematically nice.. – Alexander Chervov Jun 22 '12 at 11:33

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.

-
@Pietro thank you very much ! Very nice tricks. It seems to me the equation just genereic n-th order polynomial equation - but it is of ONE variable while the initial problem is multi-variable. – Alexander Chervov Jun 22 '12 at 15:06

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.

-
I do not quite understand. Do you mean that if the set is convex then we might find the nearest point in it to E outside it, in some simple way ? – Alexander Chervov Jun 22 '12 at 11:51
"Easy" means -- something more clever than any of standard minimization algorithms (steepest descent or whatever) - something which will take specific properties of M into account. Well I am keeping analogy with soliton equations in mind - to find such point is to solve some equations - if there are something like "soliton" like equations for this problem than one can use specific methods to solve them, rather than general numeric schemes... this analogy is very vague... – Alexander Chervov Jun 22 '12 at 12:24
In general, convex programming (in this case, minimizing a convex function on a convex set) is considered "easy" these days. Non-convex programming tends to be hard. In particular, the closest point problem on a non-convex closed set may not have a unique solution, and local optima are not necessarily global optima. – Robert Israel Jun 22 '12 at 18:53