Let $\mathcal M$ and $\mathcal N$ be two linear subspaces of $\mathbb{R}^n$ such that $\dim \mathcal M = \dim \mathcal{N}$. Such subspaces are known to be isometric: that is, there exists a bijective linear operator $T:\mathcal M\to\mathcal N$ such that $\|Tx\|=\|x\|$ for all $x\in\mathcal M$. But I want to choose such $T$ so it's not too far from the orthogonal projection onto $\mathcal N$, denoted $P_{\mathcal{N}}$. Is there an isometry $T:\mathcal M\to\mathcal N$ such that $$ \|Tx-P_\mathcal Nx\|\le \|x-P_\mathcal Nx\|\quad \forall x\in\mathcal M \tag{?} $$


Progress so far

  • If $\mathcal M \perp \mathcal N$, the answer is trivially yes: any isometry works because $P_\mathcal Nx=0$ for all $x\in \mathcal M$.

  • If $\dim \mathcal M = 1 =\dim \mathcal N$, the answer is also yes. Indeed, we can arrange for $\mathcal N$ to be the horizontal axis in $\mathbb{R}^2$, and for $\mathcal N$ to be the line $\{(t\cos \theta, t\sin\theta) : t\in\mathbb{R}\}$ where $\theta\in [0, \pi/2]$ is fixed. The isometry $(t \cos\theta, t\sin\theta)\mapsto (t, 0)$ satisfies (?) because $1-\cos \theta \le \sin\theta $.

  • It suffices to consider the case $\mathcal M\cap \mathcal N = \{0\}$. Otherwise, let $\widetilde{\mathcal M}$ be the orthogonal complement of $\mathcal M\cap \mathcal N$ in $\mathcal M$, and similarly for $\widetilde{\mathcal N}$. Pick an isometry $\widetilde{T} : \widetilde{\mathcal M} \to \widetilde{\mathcal N}$ for which (?) holds, and extend it to $T:\mathcal M\to\mathcal N$ by letting $Tx=x$ on $\mathcal M\cap \mathcal N$. Then $T$ is equivariant with respect to shifts along $\mathcal M\cap \mathcal N$, and so is $P_{\mathcal N}$, so the property (?) holds for $T$ as well.
  • “Close to orthogonal projection” is not how I’d describe the first case. – amd May 10 at 22:42
up vote 4 down vote accepted
+100

Notations

In this post, all vectors are put in the column form, and vectorization is used extensively. In case of this convention, this section briefly explains how the notations are adopted.

  • Let $\left\{\mathbf{u}_j\right\}_{j=1}^k\subseteq\mathbb{R}^n$ be an orthonormal basis for $\mathcal{M}$. Denote $U=\left(\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_k\right)\in\mathbb{R}^{n\times k}$.
  • Let $\left\{\mathbf{v}_j\right\}_{j=1}^k\subseteq\mathbb{R}^n$ be an orthonormal basis for $\mathcal{N}$. Denote $V=\left(\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_k\right)\in\mathbb{R}^{n\times k}$.
  • Let $T$ be an isometry between $\mathcal{M}$ and $\mathcal{N}$. There exists a unique $Q\in O(k)$, such that $$ \left(T(\mathbf{u}_1),T(\mathbf{u}_2),\cdots,T(\mathbf{u}_k)\right)=VQ. $$ This is because each $T(\mathbf{u}_j)\in\mathcal{N}$, for which it yields a unique linear combination of $\mathbf{v}_j$'s, i.e., $$ T(\mathbf{u}_j)=\sum_{m=1}^kq_{mj}\mathbf{v}_m=\left(\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_k\right)\left( \begin{array}{c} q_{1j}\\ q_{2j}\\ \vdots\\ q_{kj} \end{array} \right). $$ Thus put all $T(\mathbf{u}_j)$'s together, the formula reads $$ \left(T(\mathbf{u}_1),T(\mathbf{u}_2),\cdots,T(\mathbf{u}_k)\right)=\left(\mathbf{v}_1,\mathbf{v}_2,\cdots,\mathbf{v}_k\right)\left( \begin{array}{cccc} q_{11}&q_{12}&\cdots&q_{1k}\\ q_{21}&q_{22}&\cdots&q_{2k}\\ \vdots&\vdots&\ddots&\vdots\\ q_{k1}&q_{k2}&\cdots&q_{kk} \end{array} \right)=VQ, $$ where $Q=\left(q_{jm}\right)_{j,m=1}^k$. This shows the existence and the uniqueness of $Q$. Further, note that $T$ is isometric, for which $T(\mathbf{u}_j)\cdot T(\mathbf{u}_m)=\delta_{jm}$. In the matrix form, this reads $$ I_k=\left( \begin{array}{c} T(\mathbf{u}_1)^{\top}\\ T(\mathbf{u}_2)^{\top}\\ \vdots\\ T(\mathbf{u}_k)^{\top}\\ \end{array} \right)\left(T(\mathbf{u}_1),T(\mathbf{u}_2),\cdots,T(\mathbf{u}_k)\right)=\left(VQ\right)^{\top}\left(VQ\right)=Q^{\top}V^{\top}VQ=Q^{\top}Q. $$ Here $V^{\top}V=I_k$ because $\mathbf{v}_j$'s are orthonormal. Therefore, $Q\in O(k)$, where $O(k)$ denotes the orthogonal group of order $k$.
  • Let $P$ be the orthogonal projection from $\mathcal{M}$ to $\mathcal{N}$. Then $S=V^{\top}U\in\mathbb{R}^{k\times k}$ is such that $$ \left(P(\mathbf{u}_1),P(\mathbf{u}_2),\cdots,P(\mathbf{u}_k)\right)=VS. $$ The existence and the uniqueness of $S$ follows exactly from those of $T$. Further, since $P$ is an orthogonal projection, each $\mathbf{u}_j-P(\mathbf{u}_j)$ is perpendicular to $\mathcal{N}$, i.e., orthogonal to all $\mathbf{v}_j$'s. The matrix form of this property goes that $$ O=\left( \begin{array}{c} \mathbf{v}_1^{\top}\\ \mathbf{v}_2^{\top}\\ \vdots\\ \mathbf{v}_k^{\top} \end{array} \right)\left(\mathbf{u}_1-P(\mathbf{u}_1),\mathbf{u}_2-P(\mathbf{u}_2),\cdots,\mathbf{u}_k-P(\mathbf{u}_k)\right)=V^{\top}\left(U-VS\right)=V^{\top}U-S. $$ Therefore, $S=V^{\top}U$.

Equivalent Problem

Note that $\forall\mathbf{x}\in\mathcal{M}$, it yields a unique representation $$ \mathbf{x}=\left(\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_k\right)\left[\mathbf{x}\right]_{\mathcal{M}}=U\left[\mathbf{x}\right]_{\mathcal{M}}, $$ where $\left[\mathbf{x}\right]_{\mathcal{M}}$ is the coordinate vector of $\mathbf{x}$ under the assigned orthonormal basis for $\mathcal{M}$. In addition, $\mathbf{x}\in\mathcal{M}$ and $\left[\mathbf{x}\right]_{\mathcal{M}}\in\mathbb{R}^k$ are of one-to-one correspondence. Its image under $T$ reads $$ T(\mathbf{x})=T(\left(\mathbf{u}_1,\mathbf{u}_2,\cdots,\mathbf{u}_k\right)\left[\mathbf{x}\right]_{\mathcal{M}})=\left(T(\mathbf{u}_1),T(\mathbf{u}_2),\cdots,T(\mathbf{u}_k)\right)\left[\mathbf{x}\right]_{\mathcal{M}}=VQ\left[\mathbf{x}\right]_{\mathcal{M}}. $$ Similarly, its image under $P$ reads $$ P(\mathbf{x})=VS\left[\mathbf{x}\right]_{\mathcal{M}}. $$

It is also worth mentioning that an isometry $T$ and its respective orthogonal representation $Q$ are of one-to-one correspondence as well. Given an isometry $T$, it observes a unique orthogonal matrix $O$. Conversely, provided an orthogonal matrix $O$, it defines an isometry $T$.

With the above vectorized notations and understandings, the original question, to find an isometry $T:\mathcal{M}\to\mathcal{N}$ such that $$ \left\|T(\mathbf{x})-P(\mathbf{x})\right\|\le\left\|\mathbf{x}-P(\mathbf{x})\right\| $$ holds for all $\mathbf{x}\in\mathcal{M}$, witnesses the following equivalent problem.

Find $Q\in O(k)$ such that $$ \left\|VQ\left[\mathbf{x}\right]_{\mathcal{M}}-VS\left[\mathbf{x}\right]_{\mathcal{M}}\right\|\le\left\|U\left[\mathbf{x}\right]_{\mathcal{M}}-VS\left[\mathbf{x}\right]_{\mathcal{M}}\right\| $$ holds for all $\left[\mathbf{x}\right]_{\mathcal{M}}\in\mathbb{R}^k$, or equivalently, such that $$ \left\|V\left(Q-S\right)\left[\mathbf{x}\right]_{\mathcal{M}}\right\|^2\le\left\|\left(U-VS\right)\left[\mathbf{x}\right]_{\mathcal{M}}\right\|^2 $$ holds for all $\left[\mathbf{x}\right]_{\mathcal{M}}\in\mathbb{R}^k$, or equivalently (open all parentheses and rearrange the terms), such that $$ \left\|\left(Q-2S\right)\left[\mathbf{x}\right]_{\mathcal{M}}\right\|^2\le\left\|\left[\mathbf{x}\right]_{\mathcal{M}}\right\|^2 $$ holds for all $\left[\mathbf{x}\right]_{\mathcal{M}}\in\mathbb{R}^k$, or equivalently, such that $$ \left\|Q-2S\right\|_2\le 1. $$

With this in mind, it suffices to check whether or not the following statement holds true:

$$ \min\left\{\left\|Q-2S\right\|_2:Q\in O(k)\right\}\le 1. $$

Here the use of $\min$ instead of $\inf$ is due to the compactness of $O(k)$, which ensures the existence of the minimum.

Beyond the Procrustes

If the matrix $2$-norm $\left\|\cdot\right\|_2$ is replaced by the Frobenius norm $\left\|\cdot\right\|_{F}$, the equivalent problem reduces to the well-known orthogonal Procrustes problem, whose solution has been well-studied. For the operator-norm cases like the matrix $2$-norm, classical results could be find in Watson (1994) and Higham (1989).

Nevertheless, conclusions in the above references might be less helpful for the equivalent problem, because they are dealing with general $S$, regardless of the fact here that $S=V^{\top}U$. This fact secures the following argument. (Hopefully, there is no need to figure out the minimum; instead, an appropriate $Q$ that makes $\left\|Q-2S\right\|_2\le 1$ would suffice.)

Note that $S=V^{\top}U$ is a $k$-by-$k$ matrix. It yields a singular value decomposition, i.e., $$ V^{\top}U=S=A\Sigma B^{\top}, $$ where $A,B\in O(k)$, and $\Sigma$ is diagonal. Thanks to this decomposition, $$ \left\|Q-2S\right\|_2=\left\|AA^{\top}QBB^{\top}-2A\Sigma B^{\top}\right\|_2=\left\|A\left(A^{\top}QB-2\Sigma\right)B^{\top}\right\|_2=\left\|A^{\top}QB-2\Sigma\right\|_2, $$ where the last step is due to the orthogonal invariance of the matrix $2$-norm. Provided that $A,B,Q\in O(k)$, making $A^{\top}QB\in O(k)$. Thus it suffices to consider $$ \left\|\tilde{Q}-2\Sigma\right\|_2\le 1 $$ for some $\tilde{Q}\in O(k)$. Specifically, if all entries on the diagonal of $\Sigma$ are not larger than $1$ (i.e., all the singular values of $S$ are not larger than $1$), $\tilde{Q}=I_k$ would suffice to secure $$ \left\|\tilde{Q}-2\Sigma\right\|_2\le 1. $$ Hence the target reduces to show that all entries on the diagonal of $\Sigma$ are not larger than $1$.

Let $\sigma$ be a singular value of $V^{\top}U$. Since $$ U^{\top}VV^{\top}U=\left(V^{\top}U\right)^{\top}\left(V^{\top}U\right)=B\Sigma^2B^{\top}, $$ it is clear that $\sigma^2$ serves as an eigenvalue of $U^{\top}VV^{\top}U$. Consequently, there exists $\mathbf{w}\ne\mathbf{0}$ such that $$ U^{\top}VV^{\top}U\mathbf{w}=\sigma^2\mathbf{w}. $$ Without loss of generality, let $\left\|\mathbf{w}\right\|=1$. Then $$ \sigma^2=\sigma^2\mathbf{w}^{\top}\mathbf{w}=\mathbf{w}^{\top}U^{\top}VV^{\top}U\mathbf{w}=\left(V^{\top}U\mathbf{w}\right)^{\top}\left(V^{\top}U\mathbf{w}\right)=\left\|V^{\top}U\mathbf{w}\right\|^2, $$ or equivalently, $$ \sigma=\left\|V^{\top}U\mathbf{w}\right\|\le\left\|V^{\top}\right\|_2\left\|U\mathbf{w}\right\|\le\left\|V^{\top}\right\|_2\left\|U\right\|_2\left\|\mathbf{w}\right\|=\left\|V^{\top}\right\|_2\left\|U\right\|_2. $$ Note that $U^{\top}U=I_k$, for which $\left\|U\right\|_2=1$. Similarly, $V^{\top}V=I_k$. While this does not leads to $\left\|V^{\top}\right\|_2=1$ directly, it implies that all singular values of $V$ are $\pm 1$. Thus all singular values of $V^{\top}$ are also $\pm 1$, making $\left\|V^{\top}\right\|_2=1$. Therefore, the last inequality yields $$ \sigma\le\left\|V^{\top}\right\|_2\left\|U\right\|_2=1. $$ Since $\sigma$ is an arbitrarily chosen singular value of $V^{\top}U$, it follows immediately that all singular values of $V^{\top}U$ are not larger than $1$, as is expected.

I would like to thank OP (@user4412195) for commenting on an alternative proof, which is much more succinct, of the fact that all entries on the diagonal of $\Sigma$ are not larger than $1$. I would like to recommend this method here. Since this is to show that all the singular values of $S$ are not larger than $1$, it is equivalent to show that $\left\|S\right\|_2\le 1$. Thanks to the properties of the matrix norm, $$ \left\|S\right\|_2=\left\|V^{\top}U\right\|_2\le\left\|V^{\top}\right\|_2\left\|U\right\|_2=\left\|V\right\|_2=1. $$ The conclusion follows immediately.

To sum up, it has been proven that there exists some $Q\in O(k)$ such that $$ \left\|Q-2S\right\|_2\le 1, $$ where $Q$ could be obtained as follows. Let $V^{\top}U=S=A\Sigma B^{\top}$ be a singular decomposition, with $A,B\in O(k)$ and $\Sigma$ being a diagonal matrix. As per the above argument, $$ \left\|I_k-2\Sigma\right\|_2\le 1. $$ As such, $Q=AB^{\top}$ would be an orthogonal matrix that meets the need.

Acknowledgement

I would like to than OP (@user4412195) for pointing out that $\tilde{Q}=I_k$ suffices to ensure $\left\|\tilde{Q}-2\Sigma\right\|_2\le 1$, rather than my original "being a diagonal matrix with its diagonal entries being $\pm 1$". I very much appreciate OP's comment on shortening the proof of $\left\|S\right\|_2\le 1$ as well.

  • @user4412195: You are right! Thank you for correcting me. $\tilde{Q}=I_k$ would suffice. My mind was with your 1-D example where $U=(1,0)^{\top}$ and $V=(\cos\theta,\sin\theta)^{\top}$, and I forgot that when $\cos\theta<0$, it is no longer a singular value of $V^{\top}U$. I just fixed my answer accordingly. Also thank you very much for commenting on the estimate for $\left\|S\right\|_2$. I should have realized this! I just updated this part as well, including an acknowledgement in the end. Thank you :-) – hypernova May 14 at 19:03

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.