# Quadratic optimization problem with an orthogonality constraint

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

• 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.
– greg
Commented Oct 17, 2020 at 0:59
• I have dropped the constant term. Commented Oct 17, 2020 at 2:02
• Okay, now you are left with something called the Orthogonal Procrustes problem.
– greg
Commented Oct 17, 2020 at 3:24
• Quite interesting! I will check this solution. Thanks Commented Oct 17, 2020 at 4:00

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

• 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. Commented Oct 17, 2020 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. Commented Oct 17, 2020 at 22:05