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

Question

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 1

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.

Answer 2

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.