2
$\begingroup$

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) ?

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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