1

$X \in \mathbb{R}^{n\times d}$, $P \in \mathbb{R}^{n\times k}$ and $L \in \mathbb{R}^{k\times d}$.

What is the best way to solve a simple quadratic optimization problem with an orthogonality constraint:

$min_{_{P}}(\left \| X - PL \right \|_{F}^{2}) \:$ s.th $\:P^{T}P=I_{k}$

Michael
  • 125

1 Answers1

3

Because $P$ isn't square, this isn't quite the classical orthogonal Procrustes problem, but it can be transformed into a standard orthogonal Procrustes problem by 0-padding $L$. This is discussed for example in the book

Gower, John C., and Garmt B. Dijksterhuis. Procrustes problems. Oxford Statistical Science Series, Vol. 30. Oxford University Press, 2004.

Let

$ \bar{L}=\left[ \begin{array}{c} L \\ 0 \\ \end{array} \right] $

where the extra block of 0's makes $\bar{L}$ of size $n$ by $k$.

Then your original problem is equivalent to

$\min_{Q} \| X-Q\bar{L} \|_{F}^{2}$

where $Q$ is $n$ by $n$ and orthogonal. This is a standard orthogonal Procrustes problem. The solution to this is well known.

Find the singular value decomposition (SVD) of the matrix $X\bar{L}^{T}$.

$X\bar{L}^{T}=U\Sigma V^{T}$.

Then the optimal $Q$ is

$Q=UV^{T}$.

Once you've solved for $Q$, you can extract the first $k$ columns of $Q$ to obtain $P$. Note that $PL=Q\bar{L}$ because the last n-k rows of $\bar{L}$ are 0.

Depending on the sizes of the matrices, it may be helpful to use the economy-sized version of the SVD on $XL^{T}$ for this computation. If

$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 your solution is

$P=UV^{T}$.

Brian Borchers
  • 10,563
  • Is it possible to solve this problem using truncated SVD of XL'? In fact the computational complexity rises too much when we use the proposed solution. – Michael Oct 17 '20 at 21:51
  • Yes, you can use the economy-sized SVD of $XL^{T}$ to do this. I'll edit the answer to include this. – Brian Borchers Oct 17 '20 at 22:05