Lipschitz constants of projections

1.5k Views Asked by At

Consider two compact sets $A, B \subset \mathbb{R}^n$.

Assume that the projection mappings $P_A: \mathbb{R}^n \rightarrow A$, $P_B : \mathbb{R}^n \rightarrow B$ have Lipschitz constant $1$ and $L$, respectively.

What is the Lipschitz constant of the projection mapping $P_{A \cap B}$?

1

There are 1 best solutions below

3
On BEST ANSWER

The nearest point projection onto a closed subset $E\subset \mathbb R^n$ is single-valued if and only if $E$ is convex*. In this case, the Lipschitz constant is equal to $1$.

If $E$ is not convex, there is at least one point $x\in \mathbb R^n$ for which $\min_{y\in E}\|x-y\|$ is attained at more than one point. We could try to discuss the continuity of $P_E$ as a multivalued map, using the Hausdorff metric. But this turns out to be futile: since the set of points with unique nearest point projection is dense, an arbitrarily small perturbation of $x$ can change $P_E(x)$ to a singleton. Thus, $p_E$ is discontinuous when $E$ is not convex.

Therefore, under your assumptions we can say that $A$ and $B$ are convex, $L=1$, and since $A\cap B$ is also convex, $P_{A\cap B}$ is $1$-Lipschitz as well.


(*) in a Hilbert space, convexity still implies that the nearest point projection is single-valued, but the converse is an open problem (stated, e.g., on page 67 of Nonlinear Functional Analysis by Deimling).