Efficient computation of the nearest point projection in Banach spaces

Question

Given a strictly convex and reflexive Banach space $(X,\|\cdot\|)$ and a closed subspace $M$, the metric projection is defined as $$X\to M,\qquad x\mapsto \mathrm{argmin}_{y\in M} \|x-y\|.$$ I am particularly interested in the case where at least $M$ is finite dimensional. Is there an efficent way to actually calculate the metric projection, i.e. to solve the minimisation problem $$\begin{cases}\min \|x-y\| & \\ y\in M\end{cases}$$ where $x$ and $M$ are given?

Answer 1

I think that with this kind of generality it is impossible to give a standard formula to explicitly calculate a minimizer. However, there is a condition on the minimizer $y_0$ for the problem with a given $x_0$ that is:

$d(x_0,M)=||x_0-y_0||= \max \{ f(x_0):f\in M^\perp, ||f||\le1\}$

with $M^\perp=\{f\in X^*:f(m)=0 \quad\forall m\in M \}$. This is a beautiful application of convex analysis and one can find it on Brezis "Functional Analysis, Sobolev Spaces and partial Differential Equations" - chapter 1 (the equality $d(x_0,M)= \max \{ f(x_0):f\in M^\perp,||f||\le1\}$ holds in general if $X$ is just a normed vector space and $M$ need not to be closed). So with an explicit point $x_0$ and a specific norm, one finds a condition on $y_0$.

An example is in the case of $M=\ker g $ for some $g\in X^*$; then $M^\perp=(\ker g)^\perp=\{\text{linear span of } g\}$ and thus $d(x_0,M)=\bigg|\frac {1}{||g||}g(x_0)\bigg|$, that is fairly explicit.

This extends in case of $X$ that is $n$-dimensional and $M=\ker A$ with $A:X\to X$ linear. Writing $A(v)=(A^1(v),...,A^n(v))\in X$ with $A^i\in X^*$, then $M=\ker A=\ker A^1\cap ...\cap\ker A^n $ and $M^\perp=(\ker A^1)^\perp+ ...+(\ker A^n)^\perp=\{\text{linear span of }A^1,...,A^n\}$. Hence $d(x_0,M)=\max\{\sum_{i=1}^{n}\alpha_iA^i(x_0):||\sum_{i=1}^{n}\alpha_iA^i||\le 1\}$ and one can maximize the function $\sum_{i=1}^{n}\alpha_iA^i(x_0)$ as a function of $\alpha_1,...,\alpha_n$ under the constraint $||\sum_{i=1}^{n}\alpha_iA^i||\le 1$.