Quasi-projections and isometries

A typical scenario: given a subset ${E}$ of a metric space ${X}$ and a point ${x\in X}$, we look for a point ${y\in E}$ that is nearest to ${x}$: that is, ${d(x, y) = \mathrm{dist}\,(x, E)}$. Such a point is generally not unique: for example, if ${E}$ is the graph of cosine function and ${x = (\pi, \pi/2)}$, then both ${(\pi/2, 0)}$ and ${(3\pi/2, 0)}$ qualify as nearest to ${x}$. This makes the nearest-point projection onto ${E}$ discontinuous: moving ${x}$ slightly to the left or to the right will make its projection onto ${E}$ jump from one point to another. Not good.

Even when the nearest point projection is well-defined and continuous, it may not be the kind of projection we want. For example, in a finite-dimensional normed space with strictly convex norm we have a continuous nearest-point projection onto any linear subspace, but it is in general a nonlinear map.

Let’s say that ${P\colon X\to E}$ is a quasi-projection if ${d(x, P(x)) \le C \mathrm{dist}\,(x, E)}$ for some constant ${C}$ independent of ${x}$. Such maps are much easier to construct: indeed, every Lipschitz continuous map ${P\colon X\to E}$ such that ${P(x)=x}$ for ${x \in E}$ is a quasi-projection. For example, one quasi-projection onto the graph of cosine is the map ${(x, y)\mapsto (x, \cos x)}$ shown below.

If ${X}$ is a Banach space and ${E}$ is its subspace, then any idempotent operator with range ${E}$ is a quasi-projection onto ${E}$. Not every subspace admits such an operator but many do (these are complemented subspaces; they include all subspaces of finite dimension or finite codimension). By replacing “nearest” with “close enough” we gain linearity. And even some subspaces that are not linearly complemented admit a continuous quasi-projection.

Here is a neat fact: if ${M}$ and ${N}$ are subspaces of a Euclidean space and ${\dim M = \dim N}$, then there exists an isometric quasi-projection of ${M}$ onto ${N}$ with constant ${C=\sqrt{2}}$. This constant is best possible: for example, an isometry from the ${y}$-axis onto the ${x}$-axis has to send ${(0, 1)}$ to one of ${(\pm 1, 0)}$, thus moving it by distance ${\sqrt{2}}$.

Proof. Let ${k}$ be the common dimension of ${M}$ and ${N}$. Fix some orthonormal bases in ${M}$ and ${N}$. In these bases, the orthogonal (nearest-point) projection from ${M}$ to ${N}$ is represented by some ${k\times k}$ matrix ${P}$ of norm at most ${1}$. We need an orthogonal ${k\times k}$ matrix ${Q}$ such that the map ${M\to N}$ that it defines is a ${\sqrt{2}}$-quasi-projection. What exactly does this condition mean for ${Q}$?

Let’s say ${x\in M}$, ${y\in N}$ is the orthogonal projection of ${x}$ onto ${N}$, and ${z\in N}$ is where we want to send ${x}$ by an isometry. Our goal is ${\|x-z\|\le \sqrt{2}\|x-y\|}$, in addition to ${\|z\|=\|x\|}$. Squaring and expanding inner products yields ${2\langle x, y\rangle - \langle x, z \rangle \le \|y\|^2}$. Since both ${y}$ and ${z}$ are in ${N}$, we can replace ${x}$ on the left by its projection ${y}$. So, the goal simplifies to ${\|y\|^2 \le \langle y, z\rangle}$. Geometrically, this means placing ${z}$ so that its projection onto the line through ${y}$ lies on the continuation of this line beyond ${y}$.

So far so good, but the disappearance of ${x}$ from the inequality is disturbing. Let’s bring it back by observing that ${\|y\|^2 \le \langle y, z\rangle}$ is equivalent to ${4(\|y\|^2 - \langle y, z\rangle) + \|z\|^2 \le \|x\|^2}$, which is simply ${\|2y-z\| \le \|x\|}$. So that’s what we want to do: map ${x}$ so that the distance from its image to ${2y}$ does not exceed ${\|x\|}$. In terms of matrices and their operator norm, this means ${\|2P-Q\|\le 1}$.

It remains to show that every square matrix of norm at most ${2}$ (such as ${2P}$ here) is within distance ${1}$ of some orthogonal matrix. Let ${2P = U\Sigma V^T}$ be the singular value decomposition, with ${U, V}$ orthogonal and ${\Sigma}$ a diagonal matrix with the singular values of ${2P}$ on the diagonal. Since the singular values of ${2P}$ are between ${0}$ and ${2}$, it follows that ${\|\Sigma-I\|\le 1}$. Hence ${\|2P - UV^T\|\le 1}$, and taking ${Q=UV^T}$ concludes the proof.

(The proof is based on a Stack Exchange post by user hypernova.)

This site uses Akismet to reduce spam. Learn how your comment data is processed.