1
$\begingroup$

$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}$

$\endgroup$
4
  • $\begingroup$ The constraint $P^TP=I_k$ implies that $\|P\|^2_F=k$ which is a constant, so it can be dropped from the objective function. $\endgroup$
    – greg
    Commented Oct 17, 2020 at 0:59
  • $\begingroup$ I have dropped the constant term. $\endgroup$
    – Michael
    Commented Oct 17, 2020 at 2:02
  • $\begingroup$ Okay, now you are left with something called the Orthogonal Procrustes problem. $\endgroup$
    – greg
    Commented Oct 17, 2020 at 3:24
  • $\begingroup$ Quite interesting! I will check this solution. Thanks $\endgroup$
    – Michael
    Commented Oct 17, 2020 at 4:00

1 Answer 1

3
$\begingroup$

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}$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Michael
    Commented Oct 17, 2020 at 21:51
  • $\begingroup$ Yes, you can use the economy-sized SVD of $XL^{T}$ to do this. I'll edit the answer to include this. $\endgroup$ Commented Oct 17, 2020 at 22:05

You must log in to answer this question.

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