Find a matrix with orthonormal columns with minimal Frobenius distance to a given matrix

Question

Let $\mathbf A$ be an arbitrary $n \times m$ matrix with $n \ge m$. I want to find $\mathbf X$ of the same size with orthonormal columns that minimizes the Frobenius norm of the difference between $\mathbf X$ and $\mathbf A$:

$$\arg\min \|\mathbf A-\mathbf X\|_{\text F}^2 \quad \text{s.t.} \quad \mathbf X^\top\mathbf X = \mathbf I_m.$$

Alternatively and equivalently, one can ask to maximize $\operatorname{tr}(\mathbf X^\top \mathbf A)$ under the same constraint:

$$\|\mathbf A-\mathbf X\|_{\text F}^2 = \|\mathbf A\|_{\text F}^2 + m - 2\operatorname{tr}(\mathbf X^\top \mathbf A).$$

I know the solution: do a thin SVD $\mathbf Y = \mathbf{USV}^\top$ and set $\mathbf X = \mathbf U \mathbf V^\top$. Questions:

1. How to prove this fact in the most compact way possible? Does it follow from some other more well-known or "named" result (such as, e.g., the Eckart-Young theorem)?

2. Does this procedure have a name? I am thinking of something along the lines of "minimum distance orthogonalization" but I cannot find anything. At the same time I vaguely remember reading about it before. What would be the right keywords to find the solution?

Answer 1

Q1. Proof

Given $\mathbf A$ that is square or tall, we want to maximize $\operatorname{tr}(\mathbf A^\top \mathbf X)$ subject to $\mathbf X^\top \mathbf X=\mathbf I$.

Let us denote by $\mathbf A = \mathbf{USV}^\top=\mathbf{\tilde U}\mathbf{\tilde S}\mathbf V^\top$ the "thin" and the "full" SVD of $\mathbf A$. Now we have:

\begin{align} \operatorname{tr}(\mathbf X^\top \mathbf A) &= \operatorname{tr}(\mathbf X^\top \mathbf {\tilde U}\mathbf {\tilde S}\mathbf V^\top) = \operatorname{tr}(\mathbf {\tilde S} \mathbf V^\top\mathbf X^\top\mathbf{\tilde U}) \\&= \operatorname{tr}(\mathbf{\tilde S} \mathbf P) = \sum s_i P_{ii} \le \sum s_i = \operatorname{tr}(\mathbf S). \end{align}

Here what I called $\mathbf P$ is a matrix with orthonormal rows as can be verified directly: $$\mathbf P\mathbf P^\top = \mathbf V^\top\mathbf X^\top\mathbf{\tilde U} \mathbf{\tilde U}^\top \mathbf X \mathbf V = \mathbf I.$$ So $\mathbf P$ must have all its elements not larger than one. It follows that the whole expression is not larger than the sum of singular values. Using $\mathbf X = \mathbf{UV}^\top$ yields exactly this value of the trace, hence it is the optimum. QED.

(This proof can be found e.g. in Gower & Dijksterhuis, Procrustes Problems, section 5.1. The proof is a little less confusing when $\mathbf A$ is square because then the thin and the full SVDs coincide.)

---

Q2. How is it called?

Very similar problems have been studied in several different areas. I found three (!).

1. FIRST, there is orthogonal Procrustes problem: given $\mathbf A$ and $\mathbf B$, find orthogonal matrix $\boldsymbol\Omega$ minimizing $\|\mathbf A - \mathbf B\boldsymbol\Omega\|^2$. Writing it as $$\|\mathbf A - \mathbf B\boldsymbol\Omega\|^2 = \|\mathbf A\|^2 + \|\mathbf B\|^2 - 2\operatorname{tr}(\mathbf{AB}^\top\boldsymbol\Omega),$$ we see that the solution is given by the SVD of $\mathbf{AB}^\top$.

   A related problem is minimizing $\|\mathbf A - \mathbf B\boldsymbol\Omega\|^2$ when $\boldsymbol\Omega$ is not square and has orthonormal rows. It has exactly the same solution. Actually, my problem can be seen as exactly this one when $\mathbf B=\mathbf I$.

   However, when $\boldsymbol\Omega$ is not square and has orthonormal columns, the problem does not have a closed-form solution (see Procrustes Problems referenced above.)

2. SECOND, there is an orthogonalization problem: given $\mathbf A=\mathbf{USV}^\top$, find a square matrix $\boldsymbol\Omega$ that would make $\mathbf A\boldsymbol\Omega$ have orthonormal columns such that $\|\mathbf A - \mathbf A\boldsymbol\Omega\|^2$ were minimal. We already saw that the best $\mathbf A\boldsymbol\Omega$ is $\mathbf{UV}^\top$, and in order to achieve that $\boldsymbol\Omega$ should be equal to $\mathbf V\mathbf S^{-1}\mathbf V^\top = \mathbf C^{-1/2}$ where $\mathbf C = \mathbf A^\top\mathbf A$.

   This is apparently known in physical chemistry as Löwdin's symmetric orthogonalization! According to Mayer, 2002, On Löwdin's method of symmetric orthogonalization,

   Löwdin's symmetric orthogonalization scheme is well known to everybody working in quantum chemistry. It was introduced in 1950 [1] as a tool for transforming the generalized eigenvalue problem obtained in overlapping basis sets to an equivalent “standard” eigenvalue problem valid in an auxiliary orthogonal basis. (Many of us call the latter simply the “Löwdin basis.”)

   [...] In 1957 Carlson and Keller proved [2] that the symmetrically orthogonalized (or simply “Löwdin-orthogonalized”) orbitals have a remarkable property: among all the possible orthonormal functions, the symmetrically orthogonalized ones are the closest in the least-squares sense to the original nonorthogonal functions.

3. THIRD, there is a problem of whitening: given centered $\mathbf A=\mathbf{USV}^\top$, find a square matrix $\boldsymbol\Omega$ that would make $\mathbf A\boldsymbol\Omega$ have uncorrelated columns with unit variance such that $\|\mathbf A - \mathbf A\boldsymbol\Omega\|^2$ were minimal. This of course differs from symmetric orthogonalization only by a constant, and the solution is $\boldsymbol\Omega = \mathbf C^{-1/2}$ where $\mathbf C = \mathbf A^\top\mathbf A/n$ is the corresponding covariance matrix.

   This is called ZCA whitening. See my own answer in What is the difference between ZCA whitening and PCA whitening? and e.g. Kessy et al., 2018, Optimal Whitening and Decorrelation.

Answer 2

Suppose we are given (square or tall) matrix $\mathrm B \in \mathbb R^{n \times p}$, where $n \geq p$. We have the following optimization problem in semi-orthogonal matrix $\mathrm X_1 \in \mathbb R^{n \times p}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X_1 - \mathrm B \|_{\text{F}}^2\\ \text{subject to} & \mathrm X_1^\top \mathrm X_1 = \mathrm I_p\end{array}$$

Let us introduce optimization variable $\mathrm X_2 \in \mathbb R^{n \times (n-p)}$, whose $n-p$ orthonormal columns are orthogonal to the $p$ columns of $\mathrm X_1$, i.e.,

$$\begin{array}{rl} \mathrm X_2^\top \mathrm X_2 &= \mathrm I_{n-p}\\ \mathrm X_1^\top \mathrm X_2 &= \mathrm O_{p \times (n-p)}\end{array}$$

Define

$$\mathrm X := \begin{bmatrix} \mathrm X_1 & \mathrm X_2\end{bmatrix}$$

Note that

$$\mathrm X_1 = \begin{bmatrix} \mathrm X_1 & \mathrm X_2\end{bmatrix} \underbrace{\begin{bmatrix} \,\,\mathrm I_{p}\\ \mathrm O\end{bmatrix}}_{=: \mathrm A \in \mathbb R^{n \times p}} = \mathrm X \mathrm A$$

where the zero matrix is $(n-p) \times p$. Thus, we have the Orthogonal Procrustes Problem in square, orthogonal matrix $\mathrm X \in \mathbb R^{n \times n}$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X \mathrm A - \mathrm B \|_{\text{F}}^2\\ \text{subject to} & \mathrm X^\top \mathrm X = \mathrm I_n\end{array}$$

whose (well-known) solution is $\bar{\mathrm X} := \mathrm U \mathrm V^\top$, where the columns of $n \times n$ matrices $\rm U$ and $\rm V$ are the left and right singular vectors of $n \times n$ matrix $\rm B A^\top = \begin{bmatrix} \mathrm B & \mathrm O\end{bmatrix}$. Taking the first $p$ columns of $\bar{\mathrm X}$,

$$\bar{\mathrm X_1} := \mathrm U \mathrm V^\top \begin{bmatrix} \,\,\mathrm I_{p}\\ \mathrm O\end{bmatrix} = \mathrm U \mathrm V^\top \mathrm A$$

which is the solution of the initial optimization problem.