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



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


