# Matrix factorization with a semi-orthogonality constraint

Given $$X \in \mathbb{R}^{n \times d}$$, I have an optimization problem with an orthogonality constraint:

$$\min_{_{P \in \mathbb{R}^{n \times k}, L \in \mathbb{R}^{k \times d}}}\left \| X - PL \right \|_{F}^{2} \quad \text{s.t.} \quad \:P^{T}P=I_{k} \tag{1}$$

I have tried to solve problem (1) by alternating between solving problem (2) and problem (3) as follows.

## Solving P:

$$\min_{_{P \in \mathbb{R}^{n \times k}}}(\left \| X - PL \right \|_{F}^{2}) \quad \text{s.t.} \quad \:P^{T}P=I_{k} \tag{2}$$

Problem (2) is the Orthogonal Procrustes problem.

By applying compact SVD on $$XL^{T}$$, we obtain: $$XL^{T}=U\Sigma V^{T}$$ where $$U$$ is of size $$n$$ by $$k$$, $$\Sigma$$ is of size $$k$$ by $$k$$, and $$V$$ is of size $$k$$ by $$k$$. Then the solution to problem (2) is :

$$P=UV^{T}$$.

## Solving L:

$$\min_{_{L \in \mathbb{R}^{k \times d}}}(\left \| X - PL \right \|_{F}^{2}) \quad \text{s.t.} \quad P^{T}P=I_{k} \tag{3}$$

Solution of problem (3) is straightforward:

$$L = P^{T}X$$

## Question

My optimizer always converges at a local minimum. Is there another way to solve problem (1) ?

Yes, there is another way. Note that with the existence of the rank-revealing $$QR$$ factorization, we find that a matrix $$M$$ can be written in the form $$M = PL$$ with $$P$$ of size $$n \times k$$, $$L$$ of size $$k \times d$$, and $$P^TP = I$$ if and only if $$M$$ has rank at most $$k$$. With that, we can equivalently frame problem (1) as $$\min_{M}\|X - M\|_F \quad \text{s.t.} \quad \operatorname{rank}(M) \leq k. \tag{0}$$ In other words, this is simply a low-rank approximation problem. As is explained in the linked page, the EYM theorem guarantees that the minimizer $$M_*$$ can be obtained from the truncated SVD of $$X$$. That is, let $$X = U\Sigma V^{\top} \in \mathbb{R}^{n\times d}$$ be a thin singular value decomposition of $$X$$ and partition $$U$$, $$\Sigma=:\operatorname{diag}(\sigma_1,\ldots,\sigma_{\min\{n,d\}})$$, and $$V$$ as follows: $$U =: \begin{bmatrix} U_1 & U_2\end{bmatrix}, \quad \Sigma =: \begin{bmatrix} \Sigma_1 & 0 \\ 0 & \Sigma_2 \end{bmatrix}, \quad\text{and}\quad V =: \begin{bmatrix} V_1 & V_2 \end{bmatrix},$$ where $$U_1$$ is $$n\times k$$, $$\Sigma_1$$ is $$k\times k$$, and $$V_1$$ is $$d\times k$$. Then the rank-$$k$$ matrix, obtained from the truncated singular value decomposition $$M_* = U_1 \Sigma_1 V_1^{\top},$$ minimizes the objective function for (0). If we take $$P = U_1$$ and $$L = \Sigma_1V_1^\top$$, then we find that $$P$$ and $$L$$ satisfy the required constraints.