0
$\begingroup$

Let $m$ and $n$ be positive integers such that $m \ge n$, the case with $m >n$ being particularly interesting to us. The Stiefel manifold is \begin{equation} \mathbb{S}^{m, n} = \{X \in \mathbb{R}^{m\times n} : X^T X = I_n\}. \end{equation} Given matrices $A \in \mathbb{R}^{l\times n}$ and $B \in \mathbb{R}^{l \times m}$, the orthogonal Procrustes problem is \begin{equation} \mathrm{min} \{\|A- BX\|_F : X \in \mathbb{S}^{m,n}\}. \end{equation} When $l = m$ and $B = I_m$, the problem reduces to finding the projection of $A$ onto the Stiefel manifold, namely \begin{equation} \mathrm{min} \{\|A- X\|_F : X \in \mathbb{S}^{m,n}\}. \end{equation}

Question 1: Is it true (particularly when $m >n$) that the optimal value for the projection problem is \begin{equation} \mathrm{dist}(A, \mathbb{S}^{m,n}) = \| \sigma(A) - \mathbf{1} \|_2 \quad (\mathbb{R}^n \ni \mathrm{1} = [1, 1, ..., 1]), \end{equation} which is attained by \begin{equation} X^* = UV^T \end{equation} with $A = U\Sigma V^T$ being a thin singular value decomposition of $A$? Here, $U$, $\Sigma$, and $V$ lie in $\mathbb{R}^{m\times n}$, $\mathbb{R}^{n\times n}$, and $\mathbb{R}^{n\times n}$, respectively. If yes, where can I find an exact reference with a proof?

Question 2 (A generalization of Question 1). Is it true (particularly when $m >n$) that one of the optimal solutions for the orthogonal Procrustes problem is given by \begin{equation} X^* = UV^T \end{equation} with $B^TA = U\Sigma V^T$ being a thin singular value decomposition of $B^T A$? Here, $U$, $\Sigma$, and $V$ lie in $\mathbb{R}^{m\times n}$, $\mathbb{R}^{n\times n}$, and $\mathbb{R}^{n\times n}$, respectively. If yes, where can I find an exact reference with a proof? [Update (20220715): The answer is no. See my answer posted below.]

Question 3. If the Frobenius norm is changed to the induced $\ell_2$ operator norm, is the optimal solution known? If yes, where can I find an exact reference with a proof?

Thank you very much!

Remarks.

  1. [Higham, Matrix Nearness Problems and Applications, Th. 4.1] does provide a positive answer to Question 1, and even a partial answer to Question 3. However, it does not contain any proof or reference for this theorem. Even though the author is quite trustworthy, I dare not rely on solely such a reference.

  2. These orthogonal Procrustes discussed in [Absil, Mahony, Sepulchre, Optimization Algorithms on Matrix Manifolds, Sec. 2.2.2], [Horn, Johnson, Matrix Analysis, 2nd Edition, Sec. 7.4.5], and [Golub, Van Loan, Matrix Computations, 3rd Edition, Sec. 12.4.1]. However, only the solution to the balanced case ($m=n$) is mentioned. If the unbalanced case admits the same solution, why should they skip it? This fact makes me unsure about the answer to Question 2.

  3. My attempt for Question 1.

Proof (a positive answer to Question 1). Since \begin{equation} \|A - X\|_F^2 = \|A\|_F^2 +\|X\|_F^2 - 2\mathrm{Tr}(A^T X) =\|A\|_F^2 + n - 2\mathrm{Tr}(A^T X), \end{equation} minimizing $\|A-X\|_F$ is equivalent to maximizing $\mathrm{Tr}(A^T X)$. Setting $Y = U^T X V \in\mathbb{R}^{n\times n}$, we have \begin{equation} Y_{i,i} = U_i^T X V_i \le \|U_i\|_2\|X\|_2\|V_i\|_2 = 1, \quad i = 1, 2, ..., n, \end{equation} where $Y_{i,i}$ is the $(i,i)$ entry of $Y$, while $U_i$ and $V_i$ are the $i$-th column of $U$ and $V$ respectively. By straightforward calculations, \begin{equation} \begin{split} \mathrm{Tr}(A^T X) = &\mathrm{Tr}(V\Sigma U^T X) \\ = &\mathrm{Tr}(\Sigma U^T X V) \\ = &\mathrm{Tr}(\Sigma Y)\\ = & \sum_{i=1}^n \sigma_i(A) Y_{i,i}\\ \le & \sum_{i=1}^n \sigma_i(A), \end{split} \end{equation} where the equality holds when $X = X^* = UV^T$. Hence the optimality of $X^*$ is justified. Therefore, \begin{equation} \mathrm{dist}(A, \mathbb{S}^{m,n}) = \|A - UV^T\|_F = \|U\Sigma V^T - UV^T\|_F = \|\Sigma - I_n\|_F = \|\sigma(X) - \mathrm{1}\|_2. \end{equation} Q.E.D.

Of course, this proof follows quite standard techniques (it is for example almost the same as the proof on Wikipedia, which seems to assume that $m = n$ according to "This quantity $S$ is an orthogonal matrix").

However, if such a simple and clean answer to such a basic question (Question 1) is correct, it must have been included in papers and textbooks. Why could not I find such a reference? I must have overlooked something, either a flaw in my proof, or a reference.

  1. One may consider another orthogonal Procrustes problem formulated as \begin{equation} \mathrm{min} \{\|C- YD\|_F : Y \in \mathbb{S}^{m,n}\}, \end{equation} where the data is $C \in\mathbb{R}^{m\times l}$ and $D\in\mathbb{R}^{n\times l}$. In the balanced case ($m = n$), this formulation is equivalent to the abovementioned formulation with $C = A^T$, $D = B^T$, and $Y = X^T$. However, this formulation does not have a "truly unbalanced" case: if $m > n$, then we can set $\bar{D} = [D^T ~0]^T\in\mathbb{R}^{m\times l}$, and consider \begin{equation} \mathrm{min} \{\|C- Z\bar{D}\|_F : Z \in \mathbb{S}^{m,m}\}, \end{equation} the first $n$ columns of its solution being a solution to the problem with $D$ in the place of $\bar{D}$. Moreover, even if $m >n$, we can still solve the problem directly by the same technique presented above (if it is correct), noting that \begin{equation} \|C - YD\|_F^2 = \|C\|_F^2 + \|YD\|_F^2 - 2 \mathrm{Tr}(C^TYD) = \|C\|_F^2 +\|D\|_F^2 - 2\mathrm{Tr}(YDC^T). \end{equation} In this way, we find that a global solution to this problem is $Y^* = UV^T$, where $CD^T = U\Sigma V^T$ is an SVD of $CD^T$ with $U\in\mathbb{R}^{m\times n}$, $\Sigma \in \mathbb{R}^{n\times n}$, and $V \in \mathbb{R}^{n\times n}$. However, this does not answer our Question 2. In addition, the technique does not apply anymore, as $\|BX\|_F \neq \|B\|_F$.
$\endgroup$
2

2 Answers 2

0
$\begingroup$

Answer to Question 2. No. Consider \begin{equation} A = I_2, \quad B = \begin{bmatrix} 1 & 0 & 0\\ 0 & M & 0 \end{bmatrix}. \end{equation} Let $B^T A = U\Sigma V^T$ be a thin SVD of $B^TA$ with $U\in\mathbb{R}^{3\times2}$, $\Sigma \in \mathbb{R}^{2\times 2}$, and $V\in\mathbb{R}^{2\times 2}$. We will show that $\bar{X} = UV^T$ is never a global solution to \begin{equation} \min\{\|A-BX\|_F : X \in \mathbb{S}^{3,2}\}, \end{equation} as long as $M >> 1$.

Note that \begin{equation} B^T A = \begin{bmatrix} 1 & 0\\ 0 & M \\ 0 & 0 \end{bmatrix}. \end{equation} Thus $U$ must have the form of \begin{equation} U = \begin{bmatrix} W \\ 0\end{bmatrix} \quad \text{with} \quad W \in \mathbb{S}^{2,2}. \end{equation} Hence \begin{equation} \bar{X} = UV^T = \begin{bmatrix} WV^T \\ 0\end{bmatrix}. \end{equation} Therefore, \begin{equation} \begin{split} \|A - B\bar{X}\|_F &= \left\| \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} - \begin{bmatrix} 1 & 0\\ 0 & M \end{bmatrix} WV^T \right\|_F\\ &\ge -\left\| \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}\right\|_F + \left\|\begin{bmatrix} 1 & 0\\ 0 & M \end{bmatrix} WV^T \right\|_F \\ & = - \sqrt{2} + \sqrt{1 + M^2}\\ & \approx M. \end{split} \end{equation} However, taking \begin{equation} Y = \begin{bmatrix} 1 & 0\\ 0 & 0 \\ 0 & 1 \end{bmatrix} \in \mathbb{S}^{3,2}, \end{equation} we have \begin{equation} \begin{split} \|A - B\bar{X}\|_F &= \left\| \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} - \begin{bmatrix} 1 & 0\\ 0 & 0 \end{bmatrix} \right\|_F = 1 < \|A - B\bar{X}\|_F. \end{split} \end{equation}

For analysis of the unbalanced orthogonal Procrustes problem, see [Elden, Park, A Procrustes Problem on the Stiefel Manifold, 1997].

$\endgroup$
0
$\begingroup$

A positive answer to Question 1:

The answer is yes, and the proof included in the post is correct.

See a summary of related results in Section 2.1 of Tight Error Bounds for Nonnegative Orthogonality Constraints and Exact Penalties, Chen, He, and Zhang, 2022.

Indeed, the matrix $X^*$ specified in Question 1 is a projection of $X$ onto $\mathbb{S}^{m, n}$ under any unitarily invariant norm, not only the Frobenius norm. This result is due to Fan and Hoffman in the square case (see [Theorem 1, Ky Fan and A. J. Hoffman. Some metric inequalities in the space of matrices. Proc. Amer. Math. Soc., 6:111–116, 1955]).

Theorem (Fan-Hoffman 1955, see [Theorem 8.4, N. J. Higham. Functions of Matrices: Theory and Computation. SIAM, Philadelphia, 2008]). Suppose that $X = UP$ is a polar decomposition of a matrix $X \in \mathbb{R}^{m\times n}$ ($m \ge n$). Then \begin{equation} \|X - U\| = \min\{\|X - V\| \mathrel{:} V \in \mathbb{S}^{m, n}\} \end{equation} for any unitarily invariant norm.

Note that the theorem also answers Question 3.

In the sequel, I will give a brief proof of this theorem. The proof is different from the one in [Higham 2008], but the basis is the same, which is the following lemma. This lemma is due to Mirsky in the square case (see the proof of Theorem 5 in [L. Mirsky. Symmetric gauge functions and unitarily invariant norms. Q. J. Math., 11:50–59, 1960]). See my post on MathOverflow for more discussion on this lemma.

For two vectors $x$ and $y$ in $\mathbb{R}^n$, recall that $y$ weakly majorizes $x$, denoted by $x\prec_w y$, if the sum of the $k$ largest entries of $x$ is smaller than or equal to that of $y$ for each $k \in\{1, ..., n\}$. For any matrix $A$, we use $\sigma(A)$ to denote the vector consisting of the singular values of $A$ in descending order.

Lemma 1 (Mirsky 1960, see [Theorem 3.4.5, R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1994]) For any matrices $X, Y \in \mathbb{C}^{m\times n}$, we have $|\sigma(X) - \sigma(Y)| \prec_w \sigma(X-Y)$.

We also need the following fundamental results.

Lemma 2 (von Neumann 1937, see [Theorem 3.5.18, R. A. Horn and C. R. Johnson. Topics in Matrix Analysis. Cambridge University Press, Cambridge, 1994]). $\|\cdot\|$ is a unitarily invariant norm on $\mathbb{C}^{m\times n}$ ($m \ge n$) if and only if there exists a symmetric gauge function $g$ on $\mathbb{R}^n$ such that $\|X\| = g(\sigma(X))$ for all $X\in \mathbb{R}^{m\times n}$.

Lemma 3 (Fan 1951, see [Theorem 4, Ky Fan. Maximum properties and inequalities for the eigenvalues of completely continuous operators. Proc. Natl. Acad. Sci. USA, 37:760–766, 1951]). Given two nonnegative vectors $x, y \in \mathbb{R}^n$, we have $g(x) \le g(y)$ for any symmetric gauge function $g$ on $\mathbb{R}^n$ if and only if $x \prec_w y$.

Proof of the theorem. It suffices to prove that \begin{equation} \|X - U\| \le \| X - V\| \quad \text{for all} \quad V \in \mathbb{S}^{m, n}. \end{equation} According to Lemmas 2 and 3, we only need to show that \begin{equation} \sigma(X - U) \prec_w \sigma(X - V). \end{equation} To see why this inequality holds, we note that \begin{equation} (X-U)^\top (X-U) = X^\top X + U^\top U - X^\top U - U^\top X = P^2 + I - 2P = (P-I)^2, \end{equation} which implies that \begin{equation} \sigma(X-U) = \sqrt{\lambda((P-I)^2)} = |\lambda(P-I)| = |\sigma(X) - \mathbf{1}| = |\sigma(X) -\sigma(V)| \prec_w\sigma(X-V), \end{equation} where the last step invokes Lemma 1. The proof is complete.

Remark: Question 1 can also be answered by the trace inequality of von Neumann's.

Lemma 4. (Theorem 1, von Neumann 1937, see [R. D. Grigorieff. A note on von Neumann’s trace inequality. Math. Nachr., 151:327–328, 1991]) For any matrices $X \in \mathbb{C}^{m\times n}$ and $Y \in \mathbb{C}^{m\times n}$, we have $|\mathrm{tr}(X^H Y)| \le \sigma(X)^\top \sigma(Y)$.

According to Lemma 4, for any $V \in \mathbb{S}^{m, n}$, we have \begin{equation} \|X - V\|_F^2 = \|X\|_F^2 + \|V\|_F^2 - 2\mathrm{tr}(X^\top V) \ge \|\sigma(X)\|_2^2 + \|\mathbf{1}\|_2^2 - 2\sigma(X)^\top \mathbf{1} = \|\sigma(X) - \mathbf{1}\|_2^2. \end{equation}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .